BFS（幅優先探索）で無向グラフのサイクルを検出するPythonプログラム

グラフ理論における「サイクル（閉路）の検出」は、依存関係のチェックやネットワーク解析など、さまざまな場面で活用される基本的な問題です。この記事では、幅優先探索（BFS：Breadth-First Search）を使って、無向グラフにサイクルが含まれているかどうかを判定するPythonプログラムを紹介します。

サイクル検出の基本的な考え方

BFSでグラフを探索する際、各頂点を「訪問済み」としてマークしていきます。探索中に、ある頂点の隣接頂点がすでに訪問済みであり、かつその頂点が現在の頂点の親（直前にいた頂点）ではない場合、別の経路から同じ頂点へ戻ってきたことになるため、サイクルが存在すると判断できます。

また、グラフが複数の連結成分に分かれているケースにも対応できるよう、すべての頂点を順番に起点として探索を実行するのがポイントです。

サンプルコード

from collections import deque

def add_edge(adj: list, u, v):
    """無向グラフに辺(u, v)を追加する"""
    adj[u].append(v)
    adj[v].append(u)

def detect_cycle(adj: list, s, V, visited: list):
    """頂点sを起点にBFSでサイクルを検出する"""
    parent = [-1] * V
    q = deque()

    visited[s] = True
    q.append(s)

    while q:
        u = q.popleft()
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                q.append(v)
                parent[v] = u
            elif parent[u] != v:
                return True
    return False

def cycle_disconnected(adj: list, V):
    """連結していないグラフ全体に対してサイクルを調べる"""
    visited = [False] * V

    for i in range(V):
        if not visited[i] and detect_cycle(adj, i, V, visited):
            return True
    return False

if __name__ == "__main__":
    V = 5
    adj = [[] for _ in range(V)]
    add_edge(adj, 0, 1)
    add_edge(adj, 1, 2)
    add_edge(adj, 2, 0)
    add_edge(adj, 2, 3)
    add_edge(adj, 2, 1)

    has_cycle = cycle_disconnected(adj, V)

    print("グラフには5個の頂点があります")
    print("0-->1")
    print("1-->2")
    print("2-->0")
    print("2-->3")
    print("2-->1")
    print("サイクルは存在するか？")
    print("はい" if has_cycle else "いいえ")

実行結果

グラフには5個の頂点があります
0-->1
1-->2
2-->0
2-->3
2-->1
サイクルは存在するか？
はい

コードの解説

• dequeのインポート：collectionsモジュールからdequeを読み込み、BFS用のキューとして利用します。popleft()で先頭から要素を取り出すことで、幅優先の探索順序を実現しています。

• add_edge関数：隣接リスト形式のグラフに辺を追加します。無向グラフなので、u→vとv→uの両方向を登録します。

• detect_cycle関数：指定した頂点を起点にBFSを実行し、サイクルが見つかればTrueを返します。parent配列で各頂点の親を管理し、「訪問済みかつ親ではない」頂点に遭遇した時点でサイクルと判定します。

• cycle_disconnected関数：連結成分が複数あるグラフでも見落としがないよう、未訪問の頂点をすべて起点としてdetect_cycleを呼び出します。

• メイン処理：5つの頂点を持つグラフを作成し、add_edgeで辺を追加した後、cycle_disconnectedを呼び出して判定結果をコンソールに出力します。

計算量

このアルゴリズムの時間計算量は O(V + E)、必要なメモリ量（空間計算量）も O(V + E) です。ここでVは頂点数、Eは辺数を表します。各頂点と各辺を高々一度ずつ処理するため、大規模なグラフでも効率的に動作します。