【Python入門】有向グラフにサイクル（閉路）が存在するかを検出するプログラムの作り方

本記事では、「与えられた有向グラフの中にサイクル（閉路）が存在するかどうかを判定する」という問題を、Pythonを使って解決する方法を解説します。

問題の概要

問題文： 有向グラフが与えられたとき、そのグラフにサイクルが含まれているかどうかを判定してください。少なくとも1つのサイクルが存在する場合は True を、存在しない場合は False を出力します。

この問題は、グラフ理論における基本的かつ重要なトピックの一つです。例えば、タスクのスケジューリングや依存関係の管理において、循環参照（デッドロック）を検出する場面などで応用されます。

判定には深さ優先探索（DFS）を利用します。ポイントは、訪問済みノードを記録する visited 配列に加えて、現在の再帰呼び出しパス上にあるノードを記録する recStack（再帰スタック）を用意することです。探索中に再帰スタック上のノードへ再度到達した場合、そこにサイクルが存在すると判断できます。

実装例

# collectionsモジュールからdefaultdictをインポート
from collections import defaultdict

# グラフを表すクラス
class Graph():
    # コンストラクタ
    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.V = vertices

    # 辺を追加するメソッド
    def addEdge(self, u, v):
        self.graph[u].append(v)

    # DFSによるサイクル検出の補助関数
    def isCyclicUtil(self, v, visited, recStack):
        # 現在のノードを訪問済みとしてマークし、再帰スタックに追加
        visited[v] = True
        recStack[v] = True

        # 隣接ノードが訪問済みかつ再帰スタック上にあれば、サイクルが存在する
        for neighbour in self.graph[v]:
            if visited[neighbour] == False:
                if self.isCyclicUtil(neighbour, visited, recStack) == True:
                    return True
            elif recStack[neighbour] == True:
                return True

        # 再帰から抜ける際に、ノードを再帰スタックから取り除く
        recStack[v] = False
        return False

    # グラフ全体にサイクルがあるかを返すメソッド
    def isCyclic(self):
        visited = [False] * self.V
        recStack = [False] * self.V
        for node in range(self.V):
            if visited[node] == False:
                if self.isCyclicUtil(node, visited, recStack) == True:
                    return True
        return False

# 頂点4つのグラフを作成
g = Graph(4)
g.addEdge(0, 3)
g.addEdge(0, 2)
g.addEdge(3, 2)
g.addEdge(2, 0)
g.addEdge(1, 3)
g.addEdge(2, 1)

if g.isCyclic() == 1:
    print("Graph is cyclic in nature")
else:
    print("Graph is non-cyclic in nature")

実行結果

Graph is cyclic in nature

この例では、頂点 0 → 2 → 0 のような経路が存在するため、グラフにサイクルが含まれていると判定されました。

アルゴリズムのポイント

• visited配列： 一度訪れたノードを記録し、同じノードを二重に探索しないようにします。
• recStack（再帰スタック）： 現在探索中の経路上にあるノードのみを記録します。このスタック上のノードに再び到達した場合、それは「戻ってきた」ことを意味し、サイクルの存在を示します。
• 計算量： 各頂点と各辺をそれぞれ1回ずつ処理するため、時間計算量は O(V + E) です。

すべての変数はローカルスコープ内で宣言されており、その参照関係は図のように整理できます。再帰関数を抜けるタイミングで recStack[v] = False とすることで、正しくバックトラッキングが行われる点にも注目してください。

まとめ

本記事では、DFSと再帰スタックを組み合わせることで、有向グラフ内のサイクルを効率的に検出するPythonプログラムの実装方法を学びました。この手法は、依存関係の循環チェックやコンパイラの最適化処理など、さまざまな実務シーンで活用できる基礎技術です。