トポロジカルソートはDAGをソートして、右にあるノードから左へエッジが伸びないようにするソート。
アルゴリズムはこんな感じ
- 入次数が 0 のノードをすべてキューへ積む
- キューからノードを取り出す
- 取り出したノードから出ている辺を削除
- 削除した結果、入次数が0のノードが増えたらキューへ積む
- 以下キューが空になるまでくり返す
- もし、キューが空なのにまだ入次数が1以上のノードがあったらDAGではないと判断
ポイントは「入次数が0なら、そのノードは左のほうへ置いて良い」ということ。これは当然といえば当然。入次数が0なんだから、右に並べたノードから辺が伸びてくることがない。
一応コードも載せておく
void topological_sort(int N, int M, vector<int> A, vector<int> B) { vector<int> input(N, 0); // 各ノードの入次数 vector<vector<int>> edge(N, vector<int>()); rep(i, M) { edge[A[i]].push_back(B[i]); input[B[i]]++; } queue<int> q; // 入次数0のノードを積んでいくキュー rep(i, N) { if (input[i] == 0) q.push(i); } vector<int> ans; while (!q.empty()) { int p = q.front(); q.pop(); ans.push_back(p); // p から出ている辺を削除する for (const auto& e : edge[p]) { --input[e]; if (input[e] == 0) { q.push(e); } } } if ((int)ans.size() != N) { // DAG でないのでトポロジカルソートできない cout << "Not DAG!" << endl; return; } cout << "result:" << endl; for (const auto& e : ans) { cout << e << " "; } }