深さ優先探索②（Depth First Search）

問題

頂点数 $ N $、辺数 $ M $ の連結グラフが与えられます。

このグラフについて、頂点 $1$ から 頂点 $N$ までの単純パスを１つ出力してください。

解き方・ソースコード

この問題は、移動経路の軌跡をどうやって記録するかがポイントになります。

まず前回記事で実施したように隣接リストを作成してから、深さ優先探索を行います。

その過程でどの頂点をたどっているのかを $path$ に記録していき、ゴール（目的となる頂点）にたどり着いた時点で、記録してきた $path$ を出力します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#-------- 入力例１ ---------
N = 5
M = 4
edges = [(1, 3), (2, 4), (3, 4), (3, 5)]
#---------------------------
# 隣接リストを作成
g = [[] for _ in range(N)]
for edge in edges:
    a = edge[0] - 1
    b = edge[1] - 1
    g[a].append(b) # 頂点 a に隣接する頂点として b を追加
    g[b].append(a) # 頂点 b に隣接する頂点として a を追加

# 深さ優先探索
visited = [False] * N   # チェック済の頂点かどうかを管理
path = []               # 辿ってきたパスを管理

def dfs(i):
    path.append(i)      # 確認する頂点をパスに記録
    # ゴール地点にたどり着いた場合
    if i == N - 1:
        # これまでたどってきた頂点を順番に出力
        for x in path:
            print(x + 1)
        exit(0)

    # ゴールに辿りついていない場合
    visited[i] = True
    for j in g[i]:          # その頂点からつながっている頂点をチェック
        if not visited[j]:  # まだ確認していない頂点の場合
            dfs(j)          # 深さ優先探索でチェック
    path.pop()              # 一旦戻るのでチェックした頂点をパスから消去

dfs(0)

[実行結果（入力例１）]

1

3

5

頂点１⇒頂点３⇒頂点５の経路で目的の頂点に辿りつけることが確認できました。