Pythonでアルゴリズム（幅優先探索、bfs） - Qiita

はじめに pythonを使った幅優先探索の実装について解説していきます。（僕がいつも実装するやつを載せるだけです。） 幅優先探索ではよく距離についての問題が出てくるので、今回はある1頂点から各頂点までの距離を返す関数を実装します。 幅優先探索 幅優先探索に関する一般的な知識は調べればたくさん出てくると思うので、詳しくは省略しますが簡単に説明します。 青い矢印のように、近いところから順に頂点を追っていきます。今回扱う距離の場合には、ひとつ前の頂点までの距離に1を足せばいいです。（画像では1から振っていますが、距離ならば0から振ればいいです。） この頂点の探索の順番は、キューで管理します。キューは、先入れ先出しのデータ構造です。今回の例でいうと、まずはスタートの0が入ります。（[0]）次に、中身を前から取り出し、隣接する頂点を調べます。（今回は1, 2）初めて訪れたのであればキューに追加します