深さ優先探索②(Depth First Search)

問題

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

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

解き方・ソースコード

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


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

その過程でどの頂点をたどっているのかを $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
#-------- 入力例1 ---------
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)]

1

3

5

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