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

この記事は約2分で読めます。

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

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

幅優先探索の実装

[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ループを行なっていきます。

動作確認

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

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

参考書籍

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

コメント