トポロジカルソートの概要とそのプログラム

トポロジカルソートとは

閉路(頂点から辺がa→b→c→aのというようにサイクルがあるグラフのこと)のない有効グラフのことをDAGといいますが、
DAGの全ての有効辺が左から右へ向かうように、すべての頂点を水平状に並べる(各辺(u,v)について、uがvよりも先に位置するように並べる)ことを

トポロジカルソートといいます。

幅優先探索によるトポロジカルソート解説

幅優先探索で、入次数(頂点に入ってくる辺数のことで英語でindeg)が0の頂点を順番に訪問して、連結リストの末尾に追加していきます。

訪問した頂点uに探索完了フラグを立てて、その頂点からでている辺の先にある頂点vの入次数を一つ減らします。
これはその辺を削除することで対応します。

辺を削除したことで、vの入字数が0になったとき、vに訪問することができるようになるので、
vをキューに追加します。

幅優先探索によるトポロジカルソート擬似アルゴリズム

topologicalSort()
  // 全てのノードの探索フラグVを初期化
  // 全てノードについて、入次数indeg[u]を設定する
  for uが0から|V| - 1まで
    if indeg[u] == 0 && 検索フラグ == FALSE
      bfs(u)

bfs(s)
  Queue.push(s)
  V[s] = true
  while Queue not empty
    u = Queue.degueue()
    out.push_back(u)  // 次数(頂点に接合する辺の数)が0の頂点を出力用連結リストに追加

    for uに隣接するノードv
      indeg[v]--;
      if indeg[v] == 0 && V[v] == false
        V[v] = true;
        Q.enqueue(v)

AIZU ONLINE JUDGEのトポロジカルソート問題の解答

トポロジカルソートの実装例として、AIZU ONLINE JUDGEを例題にc++のコードをあげます。

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<list>
using namespace std;

static const int MAX = 100000;

vector<int>G[MAX];
list<int>Out;
bool V[MAX] = {false};
int N;
int indeg[MAX] = {0};

void bfs(int s){
    queue<int> q;
    q.push(s);
    V[s] = true;
    
    while(!q.empty()){
        int u = q.front();
        q.pop();
        Out.push_back(u);
        
        for(int i = 0;i < G[u].size();++i){
            int v = G[u][i];
            indeg[v]--;
            
            if(indeg[v] == 0 && !V[v]){
                V[v] = true;
                q.push(v);
            }
        }
    }
}

void tsort(){
    for(int u = 0;u < N;++u){
        for(int i = 0;i < G[u].size();++i){
            int v = G[u][i];
            indeg[v]++;
        }
    }
    
    for(int u = 0;u < N;++u){
        if(indeg[u] == 0 && !V[u]){
            bfs(u);
        }
    }
    
    for(list<int>::iterator it = Out.begin();it != Out.end();++it){
        cout << *it << endl;
    }
}

int main(){
    int s,t,m;
    cin >> N >> m;
    
    for(int i = 0;i < m;++i){
        cin >> s >> t;
        G[s].push_back(t);
    }
    tsort();
}

参考:プログラミングコンテスト攻略のためのアルゴリズムとデータ構造