2025.07.26（土） / 17:27

Pythonで学ぶ幅優先探索（BFS）｜基礎・最短経路・グラフ作成

これらのソースは、Pythonを用いた幅優先探索（BFS）の基本概念から、最短経路探索、実務データをグラフ構造へ変換する方法までを段階的に解説した技術ブログ記事です。

筆者が業務で幅優先探索に渡すデータを即座に作成できなかった経験を起点として、アルゴリズムの内部処理を一つずつ確認し、最終的に実際のデータから最短経路を導き出すまでの学習過程が記録されています。

幅優先探索をマスターする

最初の記事では、幅優先探索の基本的な仕組みを学んでいます。

業務中、上長から依頼された幅優先探索の第一引数に渡すデータを瞬時に作成できなかったことで、自身の実力不足を痛感したことが学習のきっかけとなっています。

dequeを使用してスタートノードをキューに追加し、先頭のノードを順番に取り出しながら探索を進めます。訪問済みのノードはsetで管理し、まだ訪問していない隣接ノードをキューへ追加します。

コードを読むだけでは理解できなかった部分について、変数の中身や処理結果を一つずつ確認しています。特に、同じノードが複数回キューへ追加された場合でも、訪問済みかどうかを判定することで重複処理を防げることを確認しています。

最初は分からなかった処理を細かく分解し、プログラムの動きを追いかけることで、BFSが近いノードから順番に探索していく仕組みを理解していく過程がまとめられています。

幅優先探索で最短経路を求める

次の記事では、基本的な幅優先探索を発展させ、スタート地点からゴール地点までの最短経路を求めています。

キューにノードだけを格納するのではなく、スタート地点から現在のノードまでに通った経路のリストを格納します。キューから取り出した経路の末尾がゴール地点と一致した時点で、その経路を戻り値として返します。

実行結果として、AからFまでの最短経路であるA → C → Fや、AからEまでのA → B → Eを確認しています。また、CからBのように到達できる経路が存在しない場合は、Noneが返されることも確認しています。

この記事では、関数の内部処理をすべて理解しようとするだけでなく、入力となる引数と出力となる戻り値を意識し、関数をブラックボックスとして組み合わせる考え方についても整理しています。

複雑な内部処理を必要な範囲で理解しながら、目的に応じて既存の関数を活用することの重要性が示されています。

幅優先探索の第一引数に渡すgraphを辞書から作成する

最後の記事では、実務で扱うような辞書形式の元データから、幅優先探索の第一引数に渡すグラフを作成しています。

元データには、接続元のnode1、接続先のnode2、接続方向を表すdirectionが格納されています。directionの値によって、接続を無視する、一方通行として登録する、双方向として登録するという処理を切り替えています。

setdefaultを使用して、ノードをキー、隣接するノードの一覧を値とする辞書を構築します。接続先を持たないノードについても、空のリストを持つキーとしてグラフ内に確保しています。

作成したグラフを最短経路探索関数へ渡す過程では、数値として定義されたノードを文字列で指定したことによるKeyErrorが発生しています。スタート地点とゴール地点を数値へ修正することでエラーを解消しました。

しかし、エラーが解消されてもノード同士が接続されていなければ、最短経路はNoneになります。そこで元データの接続関係を修正し、最終的に1000 → 1050 → 1200という最短経路を取得しています。

3つの記事を通して、幅優先探索の基本的な動作を理解するところから、最短経路を求める関数の実装、さらに実務を想定した元データからのグラフ構築へと段階的に発展しています。

単に完成したコードを掲載するのではなく、分からなかった箇所、発生したエラー、期待した結果が得られなかった原因を一つずつ確認しながら、理解を深めていく過程が記録されているのが特徴です。

全体を通して、アルゴリズムの内部処理を必要な範囲で理解しつつ、最終的には関数をブラックボックスとして活用し、実際のデータから最短経路を導き出すまでの思考プロセスがまとめられています。