深さ優先探索（通りがけ順）

深さ優先探索

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

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

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

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

ソースコード（通りがけ順）

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

[木構造]

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

通りがけ順では、２分木の左側の子ノードを先に処理し、次に右側の子ノードを処理します。

[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
# 木構造を表すデータ
#  キー：ノード番号
#  値：ノードにぶら下がっているノード
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):
    if len(tree[pos]) == 2:     # 子ノードが２つある場合
        search(tree[pos][0])
        print(pos, end=' ')     # 左のノードと右のノードの間に出力
        search(tree[pos][1])
    elif len(tree[pos]) == 1:   # 子ノードが１つある場合
        search(tree[pos][0])
        print(pos, end=' ')     # 左のノードを調べた後に出力
    else:                       # 子ノードがない場合
        print(pos, end=' ')

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

[実行結果]

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

常に左側のノード番号が優先的に出力されていることを確認できます。