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

深さ優先探索

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

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

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

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

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

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

[木構造]

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

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

行きがけ順と比べて、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が出力されることを確認できます。