- サイクルのない有向グラフを辺の向きに沿うように一列に並べること.
- ジョブのスケジューリングや, 複数のプログラムのコンパイル順序を決定する時など, 依存関係を持った処理を適切な順番に並べるときに使える.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using Graph = vector<vector<int> >; // グラフ
// トポロジカルソートする
void rec(int v, const Graph &G, vector<bool> &seen, vector<int> &order) {
seen[v] = true;
for (auto next : G[v]) {
if (seen[next]) continue; // 既に訪問済みなら探索しない
rec(next, G, seen, order);
}
order.push_back(v);
}
int main() {
int N, M; cin >> N >> M; // 頂点数と枝数
Graph G(N); // 頂点数 N のグラフ
for (int i = 0; i < M; ++i) {
int a, b;
cin >> a >> b; // ノード a からノード b へと有向辺を張る
G[a].push_back(b);
}
// 探索
vector<bool> seen(N, 0); // 初期状態では全ノードが未訪問
vector<int> order; // トポロジカルソート順
for (int v = 0; v < N; ++v) {
if (seen[v]) continue; // 既に訪問済みなら探索しない
rec(v, G, seen, order);
}
reverse(order.begin(), order.end()); // 逆順に
// 出力
for (auto v : order) cout << v << " -> ";
cout << endl;
}
- Kahnのアルゴリズムを使う方法.
- 入次数が0のノードをキューで管理する.
- 入次数が0からはじめて、次のノードの次数を一つ下げて、入次数が0になったら再びキューに入れて...を繰り返す.
- アルゴリズムビジュアル大事典p.279