C++で無向グラフ内のすべてのサイクル（閉路）を検出して出力する方法

問題の概要

この記事では、無向グラフが与えられたときに、そのグラフ内に形成されるすべてのサイクル（閉路）を検出して出力する方法を解説します。

無向グラフとは、頂点同士が双方向で接続されているグラフのことです。すべての辺に方向がなく自由に行き来できるため、「無向ネットワーク」とも呼ばれます。

サイクル（閉路）とは、グラフデータ構造において、頂点の並びが一周して出発点に戻るような閉じた経路を形成しているものを指します。

まず、具体例を見て理解を深めましょう。

入力グラフ：

出力：

Cycle 1: 2 3 4 5
Cycle 2: 6 7 8

この例では、頂点2〜5で構成されるサイクルと、頂点6〜8で構成されるサイクルの計2つが検出されています。

解決のアプローチ

この問題を解くためには、グラフのいくつかの性質を利用します。グラフ彩色法を用いて、閉路に含まれるすべての頂点を識別します。ポイントは次の通りです。

• DFS（深さ優先探索）の実行中に、探索途中の頂点（部分的に訪問済みの頂点）へ再び到達した場合、そこに閉路が存在することを意味します。
• その際は、その頂点から同じ頂点に戻ってくるまでの経路上にあるすべての頂点を、対応するサイクル番号でマークしていきます。

アルゴリズム

Step 1: 頂点を彩色しながらグラフ全体を探索するDFSトラバーサルを呼び出します。
Step 2: 探索途中の頂点が見つかった場合は、その頂点に再び到達するまでバックトラックし、
        経路上のすべての頂点にサイクル番号のカウンターでマークを付けます。
Step 3: 探索完了後、閉路を構成する辺を走査し、それらを独立した隣接リストに格納します。
Step 4: 隣接リストからサイクルを番号順に出力します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
vector<int> graph[N];
vector<int> cycles[N];
void DFSCycle(int u, int p, int color[], int mark[], int par[], int&amp; cyclenumber){
   if (color[u] == 2) {
      return;
   }
   if (color[u] == 1) {
      cyclenumber++;
      int cur = p;
      mark[cur] = cyclenumber;
      while (cur != u) {
         cur = par[cur];
         mark[cur] = cyclenumber;
      }
      return;
   }
   par[u] = p;
   color[u] = 1;
   for (int v : graph[u]) {
      if (v == par[u]) {
         continue;
      }
      DFSCycle(v, u, color, mark, par, cyclenumber);
   }
   color[u] = 2;
}
void insert(int u, int v){
   graph[u].push_back(v);
   graph[v].push_back(u);
}
void printCycles(int edges, int mark[], int&amp; cyclenumber){
   for (int i = 1; i <= edges; i++) {
      if (mark[i] != 0)
         cycles[mark[i]].push_back(i);
   }
   for (int i = 1; i <= cyclenumber; i++) {
      cout << "Cycle " << i << ": ";
      for (int x : cycles[i])
         cout << x << " ";
      cout << endl;
   }
}
int main(){
   insert(1, 2);
   insert(2, 3);
   insert(3, 4);
   insert(4, 5);
   insert(5, 2);
   insert(5, 6);
   insert(6, 7);
   insert(7, 8);
   insert(6, 8);
   int color[N];
   int par[N];
   int mark[N];
   int cyclenumber = 0;
   cout<<"Cycles in the Graph are :\n";
   int edges = 13;
   DFSCycle(1, 0, color, mark, par, cyclenumber);
   printCycles(edges, mark, cyclenumber);
}

実行結果

上記のコードをコンパイルして実行すると、次の出力が得られます。

Cycles in the Graph are :
Cycle 1: 2 3 4 5
Cycle 2: 6 7 8

コードの解説

• color[] 配列： 各頂点の探索状態を管理します（0＝未訪問、1＝探索中、2＝探索完了）。値が「1」の頂点に再び到達したことが、閉路検出の合図になります。
• par[] 配列： 各頂点の親（ひとつ前の頂点）を記録しており、閉路検出時のバックトラック処理に使用されます。
• mark[] 配列： 各頂点が何番目のサイクルに属するかを記録します。
• cyclenumber： 検出されたサイクルの総数をカウントする変数です。

このアルゴリズムの計算量はDFSの探索に依存し、頂点数をV、辺数をEとすると O(V + E) で動作するため、大規模なグラフに対しても効率的にサイクルを列挙できます。