トポロジカルソートの直観的理解

おさらい: トポロジカルソートとは

トポロジカルソートは、DAGをソートして右にあるノードから左へエッジが伸びないようにするソート。

アルゴリズムはこんな感じ

1. 入次数が 0 のノードをすべてキューへ積む
2. キューからノードを取り出す
3. 取り出したノードから出ている辺を削除
4. 削除した結果、入次数が0のノードが増えたらキューへ積む
5. 以下キューが空になるまでくり返す
6. もし、キューが空なのにまだ入次数が1以上のノードがあったらDAGではないと判断

トポロジカルソートの動作原理

ポイントは 入次数が0のノード だ。入次数が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 << " ";
  }
}