C++で有向非巡回グラフ(DAG)にトポロジカルソートを適用する方法

有向非巡回グラフ(DAG)では、トポロジカルソートを使うことで頂点を線形の順序に並べ替えることができます。

トポロジカルソートは、有向非巡回グラフ(DAG)に対してのみ機能します。また、DAGにおいてはトポロジカルソートの結果が一意になるとは限らず、複数の妥当な順序が存在することもあります。

以下のC++プログラムでは、トポロジカルソートを実行し、その結果からグラフ内に閉路(サイクル)が存在するかどうかを確認します。DAGであれば必ずトポロジカル順序が求まりますが、閉路を含むグラフでは全ての頂点を並べることができません。

アルゴリズム

Topo_Sort関数の手順

開始
    関数 Topo_Sort() を定義する
        整数型の x、ブール型配列 vstd[]、スタック Stack を宣言し、
        引数として渡す。
    vstd[x] = true を設定し、現在のノードを訪問済みとしてマークする。
    イテレータ i を宣言する。
    for (i = a[x].begin(); i != a[x].end(); ++i)
        もし (!vstd[*i]) ならば
            関数 Topo_Sort(*i, vstd, Stack) を呼び出す。
    push() 関数を呼び出して値をスタックに挿入する。
終了

サンプルコード

#include<iostream>
#include <list>
#include <stack>
using namespace std;
class grph { // グラフを表すクラス
   int ver;
   list<int> *a; // 隣接リストを格納する配列へのポインタ
   void Topo_Sort(int x, bool vstd[], stack<int> &Stack); // トポロジカルソートから利用される関数
   public:
      grph(int ver); // grphクラスのコンストラクタ
   void Insert_Edge(int x, int y); // グラフに辺を挿入する
   void Topol_Sort(); // グラフ全体のトポロジカルソートを出力する
};
grph::grph(int ver) {
   this->ver = ver;
   a = new list<int>[ver];
}
void grph::Insert_Edge(int x, int y) {
   a[x].push_back(y); // yをxのリストに追加する。
}
// Topol_Sortから呼び出される再帰関数
void grph::Topo_Sort(int x, bool vstd[], stack<int> &Stack) {
   vstd[x] = true; // 現在のノードを訪問済みとしてマークする。
   list<int>::iterator i;
   for (i = a[x].begin(); i != a[x].end(); ++i)
      if (!vstd[*i])
         Topo_Sort(*i, vstd, Stack);
   // 結果を格納するスタックに現在の頂点をプッシュする
   Stack.push(x);
}
void grph::Topol_Sort() {
   stack<int> Stack;
   // 全ての頂点を未訪問としてマークする
   bool *vstd = new bool[ver];
   for (int i = 0; i < ver; i++)
      vstd[i] = false;
   for (int i = 0; i < ver; i++)
      if (vstd[i] == false)
         Topo_Sort(i, vstd, Stack);
   while (Stack.empty() == false) {
      cout << Stack.top() << " ";
      Stack.pop();
   }
}
int main() {
   grph g(6); // 上記の図にあるグラフを作成する
   g.Insert_Edge(5, 2);
   g.Insert_Edge(5, 0);
   g.Insert_Edge(4, 0);
   g.Insert_Edge(4, 1);
   g.Insert_Edge(2, 3);
   g.Insert_Edge(3, 1);
   cout << "Topological Sort of the graph is: \n";
   g.Topol_Sort();
   return 0;
}

実行結果

Topological Sort of the graph is:
5 4 2 3 1 0

このアルゴリズムの計算量は、深さ優先探索(DFS)に基づいているため、頂点数をV、辺数をEとすると O(V + E) となります。スタックに頂点をプッシュしていく仕組みにより、依存関係の後ろ側の頂点から順に取り出され、正しいトポロジカル順序が得られます。