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

帰りがけの逆順

深さ優先探索は、再帰を使わずにループで実装することもできます。

次のサンプルコードでは、帰りがけの逆順で処理します。

[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:[]}

data = [0]
while len(data):
    pos = data.pop()    # 末尾から取り出し
    print(pos, end=' ')
    for i in tree[pos]:
        data.append(i)

[木構造]

[実行結果]

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

帰りがけ順では、深いノードが出力されたあとにその親ノードが順に出力され、最後にノード0が出力されますが、帰りがけの逆順ではその逆順で出力されていることが確認できます。