トポロジカルソート

トポロジカルソート

有向非巡回グラフ（DAG）において各ノードを順序付けしてどのノードもその出力辺の先のノードより前にくるようにならべること。

A.B.Khanのアルゴリズム

1962年にA.B.Khanが発明したアルゴリズムとのことですが、分かりやすいアルゴリズムです。

https://dl.acm.org/doi/10.1145/368996.369025

Topological Sorting is a procedure required for many problems involving analysis of networks. An example of one such problem is PERT. The present paper presents a very general method for obtaining topological order. It permits treatment of larger networks than can be handled on present procedures and achieves this with greater efficiency. Although the procedure can be adapted to any machine, it is discussed in terms of the 7090. A PERT network of 30,000 activities can be ordered in less than one hour of machine time.

30,000のアクティビティを持つPERTのトポロジカルソートをIBM7090は１時間以内にできる、としています。
IBM7090の発売時の典型的なシステム価格290万ドルぐらいだったそうです。

（入力）
辺を隣接リストで入力する。
また入力辺の数をカウントするテーブルを準備する。
入力に際し、終点側のノードのテーブルを加算（入力次数をテーブルに持つ）。

（ソート）
入力のない辺をキューに挿入。
キューが空になるまで繰り返す。

　キューから先頭の要素tempを出力しキューから除去。
　tempをcoutする。
　tempの各辺について、終点側の入力次数を１減じる（tempからくる辺を消す）。

　終点側のノードの入力次数が０になったらキューに追加する。

典型問題

AOJ GRL_4_B

https://onlinejudge.u-aizu.ac.jp/problems/GRL_4_B

コード

#include <bits/stdc++.h>
using namespace std;

int main(){
  int V,E;
  cin>>V>>E;
  
  //DAG　入力
  int t,s; 
  vector<vector<int>> G(V); 

  //ノードの入力次数を記録するテーブル
  int table[10000]={};

  for(int i=0;i<E;i++){
    cin>>s>>t;
    G[s].push_back(t);
    table[t]++; 
  }
  
  //初期の入力のない辺をキューに挿入
  queue<int>Q;
  for(int i=0;i<V;i++){
    if(table[i]==0){
      Q.push(i);
    }
  }
  
  while(Q.size() != 0){
    int temp=Q.front();
    Q.pop();
    cout<<temp<<endl;
    for(int i=0; i<G[temp].size(); i++){
      table[G[temp][i]]--;
      if(table[G[temp][i]]==0){
        Q.push(G[temp][i]);
      }
    }
  }
  return 0;
}