深さ優先探索（行きがけ順）

深さ優先探索

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

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

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

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

ソースコード（行きがけ順）

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

[木構造]

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

行きがけ順では、各ノードの子を辿る前にそのノードの一番深くまで探索を行います。

[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
# 木構造を表すデータ
#  キー：ノード番号
#  値：ノードにぶら下がっているノード
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):
    print(pos, end='　')    # 配下のノードを調べる前に出力
    for i in tree[pos]:     # 配下のノードを調べる
        search(i)           # 再帰的に探索

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

[実行結果]

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

幅優先探索とは違って、ノード0から一番深いノードまで行って上に戻り、再度別の深いノードへ進むという順番に探索されていることが確認できます。