再帰を使った無向グラフの経路全探索

book.mynavi.jp

全探索のアルゴリズムをググっていたら、無向グラフの経路を全探索するC++コードの記事がヒットしたので、 Pythonに置き換えてみました。 全ノードを訪れる経路数を数える再帰アルゴリズムです。 探索には、ノード間の接続を表す二次元テーブルと、ノードに到達した履歴を保持する配列を使用します。

# coding: utf-8

# n : ノード数
# m : パス数
n, m = map(int, input().split())

# iノード, jノードにパスがある場合はconn[i][j] = conn[j][i] = True
conn = []
for _ in [0]*n:
    conn.append([False]*n)

# iノードに訪れたことがある場合はvisited[i] = True
visited = [False] * n

# グラフ入力
# ノード番号から-1して0始まりにしておく
v = []
for _ in [0]*m:
    line = map(int, input().split())
    v.append([x-1 for x in line])

# connテーブルを初期化
for start, end in v:
    conn[start][end] = conn[end][start] = True


def dfs(now, depth):
    if visited[now]: return 0
    if depth == n - 1: return 1
    
    visited[now] = True
    ret = 0

    for i in range(0, n):
        if conn[now][i]: ret += dfs(i, depth+1)
    
    visited[now] = False

    return ret

print(dfs(0, 0))

実行例

>python hoge.py
5 5
1 2
2 3
3 4
4 5
5 2
2 #出力結果

こんなグラフを想定しています。

f:id:tx_driver:20190108232605p:plain