【Python】幅優先探索を実装する【アルゴリズム】

私自身の学習の記録用に残しておきます。

今回は幅優先探索について勉強しました。

幅優先探索の実装
参考書籍

幅優先探索の実装

tree = [[1,2],[3,4],[5,6],[7,8],[9,10],[11,12],[13,14],[],[],[],[],[],[],[],[]]
data=[0]                  #[0]dataをリストとして宣言

while len(data)>0:        #[1]dataの要素数が0よりも大きければ実行する
    pos=data.pop(0)       #[2]dataのインデックス0の要素をposに代入(初回は[1,2])
    print(pos,end='')     #[3]posの値を改行なしで表示。(初回は1)
    for i in tree[pos]:   #[4]posの値の回数だけ繰り返す
        data.append(i)    #[5]iをdataに格納

tree = [[1,2],[3,4],[5,6],[7,8],[9,10],[11,12],[13,14],[],[],[],[],[],[],[],[]]

data=[0] #[0]dataをリストとして宣言

while len(data)>0: #[1]dataの要素数が0よりも大きければ実行する

pos=data.pop(0) #[2]dataのインデックス0の要素をposに代入(初回は[1,2])

print(pos,end='') #[3]posの値を改行なしで表示。(初回は1)

for i in tree[pos]: #[4]posの値の回数だけ繰り返す

data.append(i) #[5]iをdataに格納

[0]：data=[0]は親ノード

treeは木構造内の各ノードのインデックスを表しています。

data=[0]は初めは一番上位の親ノードです。

親ノードの0には1,2、　ノード1には3,4 、　ノード2には4,5、ノード4には6,7、ノード5には8,9・・・

このように各ノードには2つの子ノードがぶら下がっています。

[1]：dataの要素が0になるまで繰り返す

whileの条件式はdataの要素が0になるまで実行することを意味しています。

今回の例では親ノードである0から14まで合わせて15個のノードがあるため、whileの中では15回の処理が行われます。

[2]posにdataのインデックス0の値を代入

変数posにdataのインデックスが0の値(一番左の値)が代入されます。

1回目のwhileループではdataには0だけなので、posには0が代入されます。

[3]posの値を出力

posの値を出力するので、初回は0が表示されます。

[4]tree[pos]の分だけ繰り返す

tree[pos]は1回目のwhileループではtree[0]、つまり[1,2]となるため、

forループでは2回処理が行われます。

[5]tree[pos]の各値をdataに格納する

forループの中で、dataへiを格納します。

初回のwhileループの中では、for i in tree[pos]の tree[pos]とは、[1,2]なので、

for i in [1,2]:であり、1,2がiに順番に代入されます。

これをforループの中でdataに代入します。

結果、1回目のwhileループが終わるとdataには1,2が格納されることになります。

この後は[2]に戻り、2回目のwhileループを行なっていきます。

動作確認

tree = [[1,2],[3,4],[5,6],[7,8],[9,10],[11,12],[13,14],[],[],[],[],[],[],[],[]]

data=[0]
while len(data)>0:
  count +=1
  pos = data.pop(0)
  print('pos',pos)                  #
  for i in tree[pos]:
    print('tree[pos]',tree[pos])    #
    data.append(i)                  
    print('data',data)              #

tree = [[1,2],[3,4],[5,6],[7,8],[9,10],[11,12],[13,14],[],[],[],[],[],[],[],[]]

data=[0]

while len(data)>0:

count +=1

pos = data.pop(0)

print('pos',pos) #

for i in tree[pos]:

print('tree[pos]',tree[pos]) #

data.append(i)

print('data',data) #

コードを見てもイマイチよくわからなかったので、#がある行にprintをいくつか挟んでみました。

pos、tree[pos]、dataについて、中身が更新される度にprintで出力してみたところ、以下のような出力となりました。

pos 0                #[3]
tree[pos] [1, 2]     #[4]
data [1, 2]          #[5]
pos 1                #[3]
tree[pos] [3, 4]     #[4]
data [2, 3, 4]       #[5]
pos 2
tree[pos] [5, 6]
data [3, 4, 5, 6]
pos 3
tree[pos] [7, 8]
data [4, 5, 6, 7, 8]
pos 4
tree[pos] [9, 10]
data [5, 6, 7, 8, 9, 10]
pos 5
tree[pos] [11, 12]
data [6, 7, 8, 9, 10, 11, 12]
pos 6
tree[pos] [13, 14]
data [7, 8, 9, 10, 11, 12, 13, 14]  #treeのインデックス7の要素にぶら下がっている要素はないため、これ以降は[4]と[5]はtree内の後半にある空のリストに対しての処理を繰り返します。
pos 7
tree[pos] []
data [8, 9, 10, 11, 12, 13, 14]
pos 8
tree[pos] []
data [9, 10, 11, 12, 13, 14]
pos 9
tree[pos] []
data [10, 11, 12, 13, 14]
pos 10
tree[pos] []
data [11, 12, 13, 14]
pos 11
tree[pos] []
data [12, 13, 14]
pos 12
tree[pos] []
data [13, 14]
pos 13
tree[pos] []
data [14]
pos 14
tree[pos] []
data []

pos 0 #[3]

tree[pos] [1, 2] #[4]

data [1, 2] #[5]

pos 1 #[3]

tree[pos] [3, 4] #[4]

data [2, 3, 4] #[5]

pos 2

tree[pos] [5, 6]

data [3, 4, 5, 6]

pos 3

tree[pos] [7, 8]

data [4, 5, 6, 7, 8]

pos 4

tree[pos] [9, 10]

data [5, 6, 7, 8, 9, 10]

pos 5

tree[pos] [11, 12]

data [6, 7, 8, 9, 10, 11, 12]

pos 6

tree[pos] [13, 14]

data [7, 8, 9, 10, 11, 12, 13, 14] #treeのインデックス7の要素にぶら下がっている要素はないため、これ以降は[4]と[5]はtree内の後半にある空のリストに対しての処理を繰り返します。

pos 7

tree[pos] []

data [8, 9, 10, 11, 12, 13, 14]

pos 8

tree[pos] []

data [9, 10, 11, 12, 13, 14]

pos 9

tree[pos] []

data [10, 11, 12, 13, 14]

pos 10

tree[pos] []

data [11, 12, 13, 14]

pos 11

tree[pos] []

data [12, 13, 14]

pos 12

tree[pos] []

data [13, 14]

pos 13

tree[pos] []

data [14]

pos 14

tree[pos] []

data []

参考書籍

こちらの本を使って勉強しています。