深さ優先探索(帰りがけ順)

深さ優先探索

目的の方へ進めるだけ進んで、進めなくなったら戻る方法を深さ優先探索といいます。

深さ優先探索は、バックトラックとも呼ばれ、すべての答えを見つけるときによく使われます。

深さ優先探索は、順番によって次の3種類があります。

🔹 行きがけ順
🔹 帰りがけ順
🔹 通りがけ順

ソースコード(帰りがけ順)

次のような木構造があるとします。

[木構造]

深さ優先探索は、再帰を使って実装するのが一般的です。

帰りがけ順では、各ノードの子をすべてたどった後でそのノードを処理します。

行きがけ順と比べて、printする位置だけが変わっています。(23行目)

[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
# 木構造を表すデータ
# キー:ノード番号
# 値:ノードにぶら下がっているノード
tree = {0:[1, 2],
1:[3, 4],
2:[5, 6],
3:[7, 8],
4:[9, 10],
5:[11, 12],
6:[13, 14],
7:[],
8:[],
9:[],
10:[],
11:[],
12:[],
13:[],
14:[]}

def search(pos):
for i in tree[pos]: # 配下のノードを調べる
search(i) # 再帰的に探索
print(pos, end=' ') # 配下のノードを調べた後に出力

search(0) # ノード0から帰りがけ順で探索

[実行結果]

7 8 3 9 10 4 1 11 12 5 13 14 6 2 0 

深いノードの番号が出力されたあとにその親ノードが順に出力され、最後にノード0が出力されることを確認できます。