グラフ探索アルゴリズムを学ぶ上で欠かせないのが「幅優先探索（BFS）」と「深さ優先探索（DFS）」です。
「BFSとDFSってどう違うの？どちらを使えばいいの？」という疑問をお持ちの方も多いでしょう。
この記事では、幅優先探索とは何か、深さ優先探索との違いについて、キュー・スタックを使った仕組みの違い・計算量・それぞれの使い所まで詳しく解説しています。
アルゴリズムの理解を深めたい方はぜひ参考にしてください。
幅優先探索（BFS）とは？基本的な意味と仕組み
それではまず、幅優先探索の基本的な意味と仕組みについて解説していきます。
幅優先探索（BFS：Breadth-First Search）とは、グラフや木構造において、起点のノードから近い順（距離の短い順）に全ノードを探索するアルゴリズムのことです。
「幅」という言葉が示す通り、木の同じ深さ（同じ階層）のノードをすべて探索してから次の深さへ進む横方向優先の探索方式です。
BFSの探索の仕組みとキューの役割
BFSでは「キュー（Queue：先入れ先出しのデータ構造）」を使って探索順序を管理します。
探索の手順は次の通りです。
BFSの探索手順：
1. 起点ノードをキューに追加し「訪問済み」にする
2. キューから先頭のノードを取り出す
3. そのノードの未訪問の隣接ノードをすべてキューに追加し「訪問済み」にする
4. キューが空になるまで2〜3を繰り返す
キューの「先入れ先出し（FIFO）」の性質により、近いノードから順番に処理されるため、BFSは自然に最短経路を発見できます。
DFS（深さ優先探索）との根本的な違い
深さ優先探索（DFS）はスタックを使って一方向に深く掘り進み、行き止まりに達したら戻ってくる縦方向優先の探索です。
| 比較項目 | BFS（幅優先探索） | DFS（深さ優先探索） |
|---|---|---|
| 探索順序 | 近い順（横方向優先） | 深い方向（縦方向優先） |
| 使うデータ構造 | キュー（Queue） | スタック（Stack）または再帰 |
| 最短経路 | 見つけられる | 保証されない |
| 時間計算量 | O(V+E) | O(V+E) |
| 空間計算量 | O(V)（最悪） | O(V)（再帰スタック） |
BFSの実装方法とコード例
続いては、BFSの実装方法とコード例を確認していきます。
PythonによるBFS実装例：
from collections import deque
def bfs(graph, start):
visited = set([start])
queue = deque([start])
while queue:
node = queue.popleft() # キューの先頭から取り出す
print(node) # 訪問したノードの処理
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
Pythonではdequeをキューとして使うことで、popleft()がO(1)で動作し効率的なBFS実装が可能です。
BFSとDFSの使い分けと適した問題の種類
続いては、BFSとDFSの使い分けと適した問題の種類を確認していきます。
BFSが適している問題
BFSは最短経路を保証できるため、迷路の最短経路・SNSでの友達の最短距離・ネットワークの最小ホップ数などの問題に適しています。
重みなしグラフにおける最短経路問題はBFSで解くのがもっとも自然です。
DFSが適している問題
DFSはすべてのノードを深く探索したい場合・位相ソート・連結成分の検出・サイクル検出などに向いています。
再帰的に実装しやすいDFSは、木の全パターン列挙や深い探索が必要な場面で力を発揮します。
まとめ
この記事では、幅優先探索（BFS）とは何か、深さ優先探索（DFS）との違いについて、仕組み・データ構造・計算量・使い分けまで詳しく解説しました。
BFSはキューを使って近い順に探索し最短経路を保証する、DFSはスタック・再帰で深く探索するというのが最も重要な違いです。
今回の内容を参考に、問題に応じてBFSとDFSを適切に使い分けられるようになりましょう。
