トポロジカルソートとは
閉路(頂点から辺が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();
}
