幅優先探索（BFS）の概念を理解した後は「実際にどう実装するの？」「計算量はどれくらい？」という具体的な疑問が出てくるでしょう。
この記事では、幅優先探索の仕組みと実装方法について、キューを使った実装の詳細・時間計算量・空間計算量・最短経路探索への応用まで詳しく解説しています。
BFSを実際のコードに落とし込んで使いこなしたい方はぜひ参考にしてください。
幅優先探索の仕組みをステップバイステップで解説
それではまず、幅優先探索の仕組みをステップバイステップで確認していきます。
BFSは「キュー（先入れ先出しのデータ構造）」を使って、起点から近い距離のノードを順番に処理していくアルゴリズムです。
グラフが次のような隣接リストで表現されているとします。
グラフの例（隣接リスト）：
graph = {
‘A’: [‘B’, ‘C’],
‘B’: [‘A’, ‘D’, ‘E’],
‘C’: [‘A’, ‘F’],
‘D’: [‘B’],
‘E’: [‘B’],
‘F’: [‘C’]
}
Aを起点とするBFSの探索順：A → B → C → D → E → F
BFSの各ステップの詳細
BFSの動作を詳細に追うと次のようになります。
ステップ1：キューに’A’を追加、訪問済みセットに’A’を登録します。
ステップ2：’A’を取り出して処理し、未訪問の隣接ノード’B’と’C’をキューに追加します。
ステップ3：’B’を取り出して処理し、未訪問の隣接ノード’D’と’E’をキューに追加します。
このように「同じ距離のノードをすべて処理してから次の距離に進む」という幅優先の順序がキューの先入れ先出し構造によって自然に実現されます。
BFSのキューを使った実装を詳しく解説
続いては、BFSのキューを使った実装を詳しく確認していきます。
グラフのBFS実装（Pythonの完全なコード例）
グラフのBFS完全実装：
from collections import deque
def bfs_full(graph, start):
visited = set() # 訪問済みノードの管理
queue = deque([start]) # 初期ノードをキューに追加
visited.add(start)
result = []
while queue:
node = queue.popleft() # FIFO：先頭から取り出す
result.append(node)
for neighbor in sorted(graph[node]): # 隣接ノードを処理
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result
最短経路を求めるBFSの実装
BFSを使って最短経路（ホップ数）を求める場合は、各ノードへの距離を記録します。
最短経路距離を求めるBFS：
def bfs_shortest_path(graph, start, goal):
queue = deque([(start, [start])]) # (現在ノード, 経路リスト)
visited = set([start])
while queue:
node, path = queue.popleft()
if node == goal:
return path # ゴールに到達したらパスを返す
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None # 到達不可能
BFSの時間計算量と空間計算量を解説
続いては、BFSの時間計算量と空間計算量を確認していきます。
時間計算量：O(V+E)
BFSの時間計算量はO(V+E)であり、Vはグラフの頂点数（Vertex）、Eは辺数（Edge）を表します。
各頂点は1回ずつキューに追加・取り出され、各辺は最大2回参照されるため（無向グラフの場合）、全体でO(V+E)となります。
密なグラフ（Eが大きい場合）では辺の数が支配的になり、疎なグラフでは頂点数が支配的になります。
空間計算量：O(V)
BFSの空間計算量はO(V)です。
キューと訪問済みセットにそれぞれ最大でV個のノードを格納するため、合わせてO(V)の追加メモリが必要です。
幅の広いグラフではキューに大量のノードが同時に存在するため、DFSと比べてメモリ使用量が多くなる傾向があります。
まとめ
この記事では、幅優先探索の仕組みと実装方法について、キューを使った実装の詳細・最短経路探索への応用・時間・空間計算量まで詳しく解説しました。
BFSはキュー（deque）を使ってO(V+E)の時間計算量で動作し、重みなしグラフの最短経路を自然に見つけられる強力なアルゴリズムです。
今回のコード例を参考に、BFSの実装を自分のプロジェクトでも活用してみてください。
