Overview
幅優先探索（BFS: Breadth-First Search） は、グラフ探索の基本中の基本。
1.幅優先探索（BFS）とは
2.BFSの基本アルゴリズム
3.BFSの代表的な応用パターン
4.典型問題を解いてみる
1. 幅優先探索（BFS）とは
BFS（Breadth-First Search） は、グラフ探索の基本アルゴリズムの1つで、「近いノード（距離が小さいノード）から順に調べる」方法。
- 主に 無向グラフ / 有向グラフの最短距離計算 に利用される
- キュー（Queue）を使って探索順を管理する
キューの記事はこちら - 迷路・地図・盤面探索 など、現実的な問題に多く登場！
使う場面
- 無重みグラフにおける 最短距離の計算
- グリッド上の最短ステップ（例：迷路）
- 到達可能性の判定（ある点から他の点に行けるか？）
計算量
- 時間計算量：O(V + E)（V: 頂点数、E: 辺の数）
- 空間計算量：O(V)（訪問管理＋キュー）
2. BFSの基本アルゴリズム
(1) アルゴリズムの流れ: キューを使って「近い順」に探索
- スタートノードをキューに入れる
- キューから取り出して、そのノードに隣接する未訪問ノードをキューに追加
- これを キューが空になるまで繰り返す
(2) 基本実装
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
print("訪問:", node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
3. BFSの代表的な応用パターン
| パターン | 説明 |
|---|---|
| 最短距離計算 | 頂点 S から各頂点までの距離を配列で持つ（例：dist[v]） |
| グリッド探索 | 迷路や盤面での上下左右移動の探索 |
| 複数始点の探索 | スタート地点が複数ある場合も同時に探索可能（初期キューに複数追加） |
| 経路復元 | prev 配列を使って、スタートからゴールまでの道を復元 |
4. 典型問題を解いてみる
例題1. センサーの島を数えよ
問題:# と . からなる H×W のグリッドが与えられる。上下左右および斜めに隣接する # を「同じ島」とみなし、島の数を数えよ。
回答
from collections import deque
H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]
visited = [[False]*W for _ in range(H)]
# 8方向（上下左右＋斜め）
dirs = [(-1,0),(1,0),(0,-1),(0,1),(-1,-1),(-1,1),(1,-1),(1,1)]
def bfs(sx, sy):
queue = deque([(sx, sy)])
visited[sx][sy] = True
while queue:
x, y = queue.popleft()
for dx, dy in dirs:
nx, ny = x+dx, y+dy
if 0<=nx<H and 0<=ny<W and not visited[nx][ny] and grid[nx][ny] == '#':
visited[nx][ny] = True
queue.append((nx, ny))
count = 0
for i in range(H):
for j in range(W):
if not visited[i][j] and grid[i][j] == '#':
bfs(i, j)
count += 1
print(count)
例題2. 魔法あり最短経路探索
問題:上下左右には通常移動（コスト0）、周囲3×3以内には「魔法」で移動（コスト1）できる迷路。スタートからゴールまでの最短回数を求めよ。
回答
from collections import deque
H, W = map(int, input().split())
CH, CW = map(lambda x: int(x)-1, input().split())
DH, DW = map(lambda x: int(x)-1, input().split())
S = [input() for _ in range(H)]
INF = 10**9
dist = [[INF]*W for _ in range(H)]
dist[CH][CW] = 0
dq = deque([(CH, CW)])
# 通常移動（コスト0）
normal = [(-1,0),(1,0),(0,-1),(0,1)]
while dq:
x, y = dq.popleft()
for dx, dy in normal:
nx, ny = x+dx, y+dy
if 0<=nx<H and 0<=ny<W and S[nx][ny]=='.' and dist[nx][ny] > dist[x][y]:
dist[nx][ny] = dist[x][y]
dq.appendleft((nx, ny))
# 魔法移動（コスト+1）
for dx in range(-2, 3):
for dy in range(-2, 3):
nx, ny = x+dx, y+dy
if 0<=nx<H and 0<=ny<W and S[nx][ny]=='.' and dist[nx][ny] > dist[x][y] + 1:
dist[nx][ny] = dist[x][y] + 1
dq.append((nx, ny))
print(dist[DH][DW] if dist[DH][DW] != INF else -1)
例題3. Snukeの順にたどる迷路
問題:グリッドには s, n, u, k, e の文字が並ぶ。スタートから "snuke" の順でたどれるかを BFS で判定せよ。
回答
from collections import deque
H, W = map(int, input().split())
grid = [input() for _ in range(H)]
order = "snuke"
visited = [[False]*W for _ in range(H)]
dq = deque()
if grid[0][0] == "s":
dq.append((0, 0, 0)) # (x, y, 今の文字番号)
visited[0][0] = True
directions = [(-1,0),(1,0),(0,-1),(0,1)]
while dq:
x, y, t = dq.popleft()
for dx, dy in directions:
nx, ny = x+dx, y+dy
if 0<=nx<H and 0<=ny<W and not visited[nx][ny]:
if grid[nx][ny] == order[(t+1)%5]:
visited[nx][ny] = True
dq.append((nx, ny, (t+1)%5))
print("Yes" if visited[H-1][W-1] else "No")
例題4. 複数の始点からの最短距離
問題:複数のスタート地点があり、それぞれの地点から BFS を同時にスタートし、各ノードまでの最短距離を求める。
回答
from collections import deque
N, M, K = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
a, b = map(lambda x: int(x)-1, input().split())
graph[a].append(b)
graph[b].append(a)
from_start = list(map(lambda x: int(x)-1, input().split()))
dist = [-1] * N
dq = deque()
for s in from_start:
dist[s] = 0
dq.append(s)
while dq:
v = dq.popleft()
for nv in graph[v]:
if dist[nv] == -1:
dist[nv] = dist[v] + 1
dq.append(nv)
print(*dist)