有向グラフのサイクル検出：DFSと白・灰・黒の3セットを使ったアルゴリズム解説

有向グラフのサイクル検出とは

深さ優先探索（DFS）の走査アルゴリズムを利用すると、有向グラフ内のサイクル（閉路）を検出できます。あるノードに自己ループ（自分自身への辺）が存在する場合はそれがサイクルとみなされ、また、子ノードから親ノードへ戻る辺が存在する場合も同様にサイクルと判定されます。

グラフが非連結（分断されたグラフ）の場合、複数の木が存在することになり、これら全体を「森」と呼びます。この場合、森を構成するすべての木についてサイクルの検出を行う必要があります。

白・灰・黒の3つのセットによるアプローチ

この手法では、DFS走査を実行する際に、ノードを3つの異なるセットに割り当てて管理します。3つのセットとは「白（White）」「灰（Grey）」「黒（Black）」です。

• 白セット：最初はすべてのノードが白セットに格納されます（未訪問の状態）。
• 灰セット：新しいノードを訪問すると、そのノードは白セットから削除され、灰セットに移動します（探索中の状態）。
• 黒セット：バックトラッキングが完了し、そのノードの処理が終わると、灰セットから黒セットへ移動します（探索完了の状態）。

灰セットに含まれるノードに再び到達した場合、それは探索中の経路上へ戻ってきたことを意味するため、サイクルが存在すると判定できます。

入力と出力

入力：隣接行列

0 1 0 0 0
0 0 0 0 0
1 0 0 1 0
0 0 0 0 1
0 0 1 0 0

出力：
The graph has cycle.（グラフにはサイクルが存在します）

アルゴリズム

dfs(curr, wSet, gSet, bSet)

入力：現在のノード、白セット、灰セット、黒セット

出力：サイクルが存在する場合は true

Begin
   現在のノード curr を白セットから削除し、灰セットに追加する
   グラフ内で curr に接続されているすべてのノード v について、以下を繰り返す
      v が黒セットに含まれる場合
         以降の処理をスキップし、次の反復へ進む
      v が灰セットに含まれる場合
         true を返す（サイクルを検出）
      dfs(v, wSet, gSet, bSet) の結果が true の場合
         true を返す
   繰り返し終了
   curr を灰セットから削除し、黒セットに追加する
   false を返す
End

hasCycle(graph)

入力：与えられたグラフ

出力：グラフにサイクルが存在する場合は true

Begin
   最初にすべてのノードを白セットに挿入する
   白セットに要素が残っている間、以下を繰り返す
      グラフ内のすべてのノード v について、以下を繰り返す
         v が白セットに含まれる場合
            dfs(v, wSet, gSet, bSet) の結果が true なら
               true を返す
      繰り返し終了
   繰り返し終了
   false を返す
End

サンプルコード（C++）

#include<iostream>
#include<set>
#define NODE 5
using namespace std;

int graph[NODE][NODE] = {
   {0, 1, 0, 0, 0},
   {0, 0, 0, 0, 0},
   {1, 0, 0, 1, 0},
   {0, 0, 0, 0, 1},
   {0, 0, 1, 0, 0}
};

bool dfs(int curr, set<int>&wSet, set<int>&gSet, set<int>&bSet) {
   // curr を白セットから灰セットへ移動
   wSet.erase(wSet.find(curr));
   gSet.insert(curr);

   for(int v = 0; v < NODE; v++) {
      if(graph[curr][v] != 0) {     // すべての隣接頂点に対して
         if(bSet.find(v) != bSet.end())
            continue;     // 頂点が黒セットに含まれる場合はスキップ
         if(gSet.find(v) != gSet.end())
            return true;     // サイクルが存在
         if(dfs(v, wSet, gSet, bSet))
            return true;     // サイクルが見つかった
      }
   }

   // curr を灰セットから黒セットへ移動
   gSet.erase(gSet.find(curr));
   bSet.insert(curr);
   return false;
}

bool hasCycle() {
   set<int> wSet, gSet, bSet;     // 白・灰・黒の3つのセット
   for(int i = 0; i<NODE; i++)
      wSet.insert(i);     // 最初にすべてのノードを白セットに追加

   while(wSet.size() > 0) {
      for(int current = 0; current < NODE; current++) {
         if(wSet.find(current) != wSet.end())
            if(dfs(current, wSet, gSet, bSet))
               return true;
      }
   }
   return false;
}

int main() {
   bool res;
   res = hasCycle();
   if(res)
      cout << "The graph has cycle." << endl;
   else
      cout << "The graph has no cycle." << endl;
}

実行結果

The graph has cycle.

計算量について

このアルゴリズムの計算量は、隣接行列を用いた場合 O(V²)、隣接リストを用いた場合は O(V + E) となります。ここで V は頂点数、E は辺の数です。各ノードは白→灰→黒の順に一度ずつ状態が変化するため、非効率な再訪問が発生せず、グラフ全体を線形時間で走査できる点がこの手法の大きな特徴です。