【C++】DFSを使って有向非巡回グラフ（DAG）のトポロジカルソートを実装する方法

有向非巡回グラフ（DAG：Directed Acyclic Graph）のトポロジカルソートとは、すべての有向辺 u → v において、頂点 u が必ず頂点 v よりも前に配置されるような、頂点の線形順序のことです。グラフが DAG でない場合（閉路を含む場合）、トポロジカルソートは定義上成立しません。

本記事では、深さ優先探索（DFS）を再帰的に適用し、探索が完了した頂点をスタックに積んでいくことで、トポロジカルソートを実現する C++ プログラムを解説します。

アルゴリズムの流れと擬似コード

DFS を利用したトポロジカルソートは、以下の手順で実行します。

Begin
    function topologicalSort():
    a) 現在のノードを訪問済みとしてマークする。
    b) この頂点に隣接するすべての頂点に対して再帰的に処理を行う。
    c) 現在の頂点を、結果を格納するスタックにプッシュする。
End

Begin
    再帰関数 topologicalSort() を呼び出す function topoSort()：
    a) すべての頂点を「未訪問」としてマークする。
    b) 関数 topologicalSort() を呼び出す。
    c) スタックの内容を出力する。
End

DFS の性質上、ある頂点から到達できるすべての頂点の処理が完了した後にその頂点をスタックへ積むため、スタックから取り出した順序がそのままトポロジカル順序になります。

C++ による実装例

#include<iostream>
#include <list>
#include <stack>
using namespace std;

class G {
   int n;
   list<int> *adj;
   // 関数の宣言
   void topologicalSort(int v, bool visited[], stack<int> &Stack);
   public:
      G(int n); // コンストラクタ
      void addEd(int v, int w);
      void topoSort();
};

G::G(int n) {
   this->n = n;
   adj = new list<int>[n];
}

// グラフに辺を追加する
void G::addEd(int v, int w) {
   adj[v].push_back(w); // v の隣接リストに w を追加
}

void G::topologicalSort(int v, bool visited[], stack<int> &Stack) {
   visited[v] = true; // 現在のノードを訪問済みとしてマーク
   list<int>::iterator i;
   // この頂点に隣接するすべての頂点に対して再帰処理
   for (i = adj[v].begin(); i != adj[v].end(); ++i)
      if (!visited[*i])
         topologicalSort(*i, visited, Stack);
   Stack.push(v); // 現在の頂点をスタックにプッシュ
}

void G::topoSort() {
   stack<int> Stack;
   bool *visited = new bool[n];
   // すべての頂点を未訪問として初期化
   for (int i = 0; i < n; i++)
      visited[i] = false;
   // 未訪問の頂点を起点に DFS を実行
   for (int i = 0; i < n; i++)
      if (visited[i] == false)
         topologicalSort(i, visited, Stack);
   // スタックの内容を取り出しながら表示
   while (Stack.empty() == false) {
      cout << Stack.top() << " "; // 要素の出力
      Stack.pop();
   }
}

int main() {
   G g(6);
   g.addEd(4, 2);
   g.addEd(5, 1);
   g.addEd(4, 0);
   g.addEd(3, 1);
   g.addEd(1, 3);
   g.addEd(3, 2);
   cout << "Topological Sort of the given graph \n";
   g.topoSort();
   return 0;
}

実行結果

Topological Sort of the given graph
5 4 1 3 2 0

計算量について

このアルゴリズムは各頂点と各辺をそれぞれ一度だけ訪問するため、頂点数を V、辺数を E とすると、計算量は O(V + E) となります。隣接リストを用いた DFS ベースの実装として非常に効率的で、大規模なグラフにも対応できます。