無向グラフのサイクル検出アルゴリズム：DFS探索を使った判定方法とC++実装

無向グラフの中にサイクル（閉路）が存在するかどうかを判定するには、DFS（深さ優先探索）によるグラフ走査を利用します。基本的な考え方は次のとおりです。

訪問済みの各頂点 v について、隣接する頂点 u を発見したとき、その u がすでに訪問済みであり、かつ u が頂点 v の親ではない場合、そこにサイクルが存在すると判断できます。

なお、本記事では説明を簡潔にするため、任意の2つの頂点間に平行辺（多重辺）は存在しないものと仮定します。

入力と出力の例

入力（隣接行列）:
      0 1 0 0 0
      1 0 1 1 0
      0 1 0 0 1
      0 1 0 0 1
      0 0 1 1 0

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

アルゴリズム

dfs（頂点, 訪問済み集合, 親）

入力： 開始頂点、訪問済み頂点の集合、その頂点の親ノード
出力： サイクルが見つかれば true

Begin
    頂点を訪問済み集合に追加する
    頂点に隣接するすべての頂点 v に対して、以下を繰り返す
        もし v が親と等しければ、スキップして次へ進む
        もし v がすでに訪問済みであれば、true を返す
        もし dfs(v, visited, vertex) が true であれば、true を返す
    繰り返し終了
    false を返す
End

hasCycle（グラフ）

入力： 対象となるグラフ
出力： サイクルが見つかれば true

Begin
    グラフ内のすべての頂点 v に対して、以下を繰り返す
        もし v がすでに訪問済みであれば、次の反復へ進む
        もし dfs(v, visited, φ) が true であれば、true を返す
              // 開始頂点 v の親は null（存在しない）
    繰り返し終了
    false を返す
End

C++による実装例

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

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

bool dfs(int vertex, set<int>&visited, int parent) {
    visited.insert(vertex);
    for(int v = 0; v<NODE; v++) {
        if(graph[vertex][v]) {
            if(v == parent)    // v が親の場合はその方向へは進まない
                continue;
            if(visited.find(v) != visited.end())    // v がすでに訪問済みの場合
                return true;
            if(dfs(v, visited, vertex))
                return true;
        }
    }
    return false;
}

bool hasCycle() {
    set<int> visited;    // 訪問済み頂点の集合
    for(int v = 0; v<NODE; v++) {
        if(visited.find(v) != visited.end())    // v が訪問済みなら次の反復へ
            continue;
        if(dfs(v, visited, -1)) {    // 開始頂点に親はないため -1 を指定
            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.

このプログラムでは、隣接行列で表現されたグラフを対象に、未訪問の頂点を起点として DFS を実行します。探索中に「訪問済みかつ親ではない」隣接頂点を見つけた時点でサイクルの存在が確定するため、非連結グラフに対してもすべての頂点を走査することで正しく判定できます。