幅優先探索（木構造）

幅優先探索

捜索を開始するところから近いものをリストアップし、それぞれを細かく調べていく方法を幅優先探索といいます。

本を読むときに目次を見て全体を把握し、さらにそれぞれの章について概要を読み、さらに内容を読む、というように徐々に深く読んでいくようなイメージです。

ソースコード

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

[木構造]

この木構造について、ノード0（一番上のノード）から順番に幅優先探索を行います。

探索を開始するところから近いものをリストアップし、さらにそれぞれを細かく調べていきます。

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

# 幅優先探索
data = [0]      # 探索を開始するノードを設定
while len(data) > 0:
    pos = data.pop(0)       # 先頭ノードを取り出し
    print(pos, end=' ')
    for i in tree[pos]:     # そのノードにぶら下がっているノードを
        data.append(i)      # リストの後ろに追加

[実行結果]

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

リストのインデックスを順番に出力しており、木構造を上から順に出力していることが分かります。