幅優先探索（BFS）とは何ですか？

Question

幅優先探索（BFS）とは何ですか？

Accepted Answer

**BFS** はグラフをレベルごとに探索し、ノードのすべての隣接ノードを訪問した後にさらに深く進みます。**キュー**を使用し、重み付けされていないグラフで**最短経路**（最小エッジ数）を見つけます。

## 考え方

ソースから開始し、それをエンキューしてから、繰り返しノードをデキューし、訪問していない隣接ノードを訪問してエンキューします。`visited` セットは再訪問を防ぎます。

## 例

```python
from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()        # FIFO: explore nearest first
        order.append(node)
        for nbr in graph[node]:
            if nbr not in visited:
                visited.add(nbr)
                queue.append(nbr)
    return order

graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
bfs(graph, 'A')                        # -> ['A', 'B', 'C', 'D']
```

## 計算量

- **時間:** O(V + E) — 各頂点とエッジを 1 回。
- **空間:** O(V) — キューと visited セット用。

## 使用時期 / 落とし穴

**重み付けされていないグラフでの最短経路**、レベル順の走査、連結成分の探索に BFS を使用します。DFS よりも多くのメモリを使用します（一度に全フロンティア）。`visited` を常に追跡しない限り、サイクルで無限ループする可能性があります。

## なぜ重要なのか

BFS はすべてのエッジが等しく重要な場合の最短経路のための *標準的な* アルゴリズムです — ルーティング、ウェブクローリング、ソーシャルネットワークの分離度。

キューベースのレベルごと構造は、基本的なトラバーサルパターンです。

BFS と DFS を知ることで、到達可能性、経路、順序付け問題に適切なツールを選択できます。