はじめに
「幅優先探索（BFS: Breadth-First Search）」は、たくさんの選択肢の中から目的のものを探し出すための基本的なアルゴリズムの一つです。 グラフや木構造と呼ばれるデータ構造を探索する際に使われます。 身近な例で言えば、SNSで「友達の友達」を順番にたどっていくようなイメージや、カーナビが最短経路を探すときにもこの考え方が応用されています。
幅優先探索の仕組み
幅優先探索は、まるで水面に広がる波紋のように、中心から外側に向かって順番に探索を進めていきます。 そのため、「横型探索」とも呼ばれます。 この動きを実現するために、「キュー（Queue）」というデータ構造が重要な役割を果たします。
キューとは？
キューは「先入れ先出し（FIFO: First-In, First-Out）」の原則でデータを管理する箱のようなものです。 スーパーのレジ待ち行列と同じで、先に並んだ人（データ）から順番に処理されます。
アルゴリズムの手順
幅優先探索は、以下のステップで進められます。
- スタート地点をキューに入れる: まず、探索を開始するノード（頂点）をキューに入れ、訪問済みとして記録します。
- キューから取り出す: キューの先頭からノードを一つ取り出します。
- 隣接ノードを調べる: 取り出したノードに隣接していて、まだ訪問していないノードをすべて見つけます。
- キューに入れる: 見つけた未訪問のノードをすべてキューの末尾に追加し、それぞれを訪問済みとして記録します。
- 繰り返す: キューが空になるまで、ステップ2から4を繰り返します。
この手順により、スタート地点から距離が1のノード、次に距離が2のノード、というように、近い順に網羅的に探索が行われます。
幅優先探索の得意なこと（応用例）
幅優先探索の「近い順に探索する」という特性は、さまざまな問題解決に応用されています。
最短経路問題（重みなしグラフ）
すべての経路のコスト（重み）が同じである場合、幅優先探索は最初に見つけたゴールまでの経路が必ず最短経路になります。 これは、近い場所から順番に調べていくため、遠回りの経路より先にゴールにたどり着くからです。
- 迷路の最短ルート探索: スタートからゴールまで、最も少ないマス数でたどり着くルートを見つけます。
- 乗り換え案内の最短回数検索: ある駅から目的の駅まで、最も乗り換え回数が少ない経路を探します。
その他の応用例
- ウェブクローラー: あるウェブページからリンクをたどり、ウェブサイト全体を効率的に巡回して情報を収集します。
- ソーシャルネットワークのつながり解析: 自分から特定の人物まで「友達の友達…」が何人介在するかを調べるのに使えます。
- パズルゲームの最短手順: ルービックキューブなど、最短で解く手順を見つける問題にも利用されます。
幅優先探索と深さ優先探索の違い
幅優先探索(BFS)としばしば比較されるのが「深さ優先探索(DFS)」です。深さ優先探索は、行けるところまで深く進み、行き止まりになったら戻って別の道を探す方法です。
| 特徴 | 幅優先探索 (BFS) | 深さ優先探索 (DFS) |
|---|---|---|
| 探索方法 | 近くから順に、横に広く探索する。 | 行けるところまで、縦に深く探索する。 |
| 使用するデータ構造 | キュー (Queue) | スタック (Stack) または 再帰関数 |
| 得意なこと | 最短経路の探索（重みなしグラフ） | 解が存在するかどうかの確認、連結成分の分解など |
| メモリ消費 | 探索範囲が広いと大きくなりがち。 | 経路が深い場合に大きくなることがあるが、一般的にBFSよりは少ない傾向。 |
Pythonによる実装例
実際にPythonで幅優先探索を実装してみましょう。ここでは、グラフを辞書型で表現し、スタート地点から各地点までの最短距離を求めます。
from collections import deque
def bfs(graph, start):
"""
幅優先探索（BFS）を行い、スタート地点から各ノードへの最短距離を返す関数
:param graph: グラフを表す隣接リスト（辞書型）
:param start: 探索を開始するノード
:return: スタートからの最短距離を格納した辞書
"""
# 訪問済みのノードを管理するキュー
queue = deque([start])
# スタート地点から各ノードへの距離を格納する辞書
# 未訪問のノードは-1で初期化
distances = {node: -1 for node in graph}
distances[start] = 0
while queue:
# キューの先頭からノードを取り出す
current_node = queue.popleft()
print(f"現在地: {current_node}, 距離: {distances[current_node]}")
# 隣接するノードを調べる
for neighbor in graph[current_node]:
# 未訪問の場合
if distances[neighbor] == -1:
# 距離を更新
distances[neighbor] = distances[current_node] + 1
# キューに次の探索候補として追加
queue.append(neighbor)
return distances
# グラフの定義（隣接リスト）
# 'A': ['B', 'C'] は、AからBとCに道があることを示す
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
# 'A'をスタート地点としてBFSを実行
start_node = 'A'
shortest_distances = bfs(graph, start_node)
print("\n--- 結果 ---")
for node, distance in shortest_distances.items():
print(f"ノード{node} までの最短距離: {distance}")
まとめ
幅優先探索（BFS）は、スタート地点から近い順に網羅的に探索するアルゴリズムです。 このシンプルな特性により、重みのないグラフにおける最短経路問題など、多くの場面で非常に強力なツールとなります。 アルゴリズムの基本的な考え方として、ぜひ覚えておきましょう。