Pythonでグラフに奇数長の閉路（サイクル）が存在するか判定するプログラム

問題概要

無向グラフが与えられたとき、そのグラフの中に奇数長の閉路（サイクル）が存在するかどうかを判定します。

例えば、次のような隣接リストが入力として与えられたとします。

adj_list = [[1, 2], [0, 3, 4], [0, 3, 4], [1, 2, 4], [1, 2, 3]]

この場合、[0, 1, 3, 4, 2]、[1, 3, 4]、[2, 3, 4] のような奇数個の頂点からなる閉路が存在するため、出力は True になります。

アルゴリズム（DFSによる解法）

この問題は深さ優先探索（DFS）を用いて効率的に解けます。ポイントは、現在探索中のパス上で各ノードの位置（インデックス）を記録しておき、同じノードに再び到達したときのインデックス差が奇数であれば、そこに奇数長の閉路が存在すると判断することです。

具体的な手順は以下の通りです。

1. dfs(node, i) 関数を定義します。node は現在のノード、i は探索の深さ（ステップ数）です。
2. node がすでに現在のパス（path）に含まれている場合は、(i − path[node]) が奇数であれば True を、偶数であれば False を返します。
3. node がすでに訪問済みの場合は False を返します。
4. node を訪問済みとしてマークし、path[node] = i を記録します。
5. arr[node] 内の各隣接ノード c に対して dfs(c, i + 1) を再帰的に呼び出し、True が返ってきたらそのまま True を返します。
6. 探索が完了したら path から node を削除してバックトラックし、False を返します。

メイン処理では以下を実行します。

• visited（訪問済みノードの集合）と path（現在のパスを表す辞書）を初期化します。
• すべてのノード i について dfs(i, 0) を呼び出し、True が返れば True を返します。
• すべてのノードを調べて閉路が見つからなければ False を返します。

Python実装例

以下の実装を見ると理解が深まります。

class Solution:
    def solve(self, arr):
        def dfs(node, i):
            if node in path:
                return (i - path[node]) % 2 == 1
            if node in visited:
                return False
            visited.add(node)
            path[node] = i
            for c in arr[node]:
                if dfs(c, i + 1):
                    return True
            del path[node]
            return False
        visited, path = set(), {}
        for i in range(len(arr)):
            if dfs(i, 0):
                return True
        return False
ob = Solution()
adj_list = [[1, 2], [0, 3, 4], [0, 3, 4], [1, 2, 4], [1, 2, 3]]
print(ob.solve(adj_list))

入力

[[1, 2], [0, 3, 4], [0, 3, 4], [1, 2, 4], [1, 2, 3]]

出力

True

補足：二部グラフとの関係

グラフ理論では、「グラフが二部グラフである」ことと「奇数長の閉路を含まない」ことは同値であることが知られています。そのため、各ノードを2色で塗り分ける二部グラフ判定アルゴリズム（BFS/DFSによる彩色）を使っても、同様に奇数長の閉路の有無を判定できます。塗り分けに失敗した時点で奇数長の閉路が存在すると分かるため、状況に応じてこちらのアプローチも検討するとよいでしょう。