幅優先探索（BFS）- 初心者向け完全ガイド
1. 幅優先探索とは何か？
幅優先探索（Breadth-First Search, BFS）は、グラフやツリーなどのデータ構造を探索するためのアルゴリズムです。名前の通り「幅優先」、つまり横方向に優先的に探索を行います。
1.1 基本概念
幅優先探索は以下のような特徴を持ちます：
- 層ごとの探索: 開始地点から距離が近い順に探索します
- キュー（Queue）を使用: 先入れ先出し（FIFO: First-In-First-Out）のデータ構造を使用します
- 最短経路の保証: 全ての辺の重みが等しい場合、最短経路を見つけることができます
- 発見順序: 開始地点からの距離順に頂点を発見します
1.2 日常生活の例え
幅優先探索は、以下のような日常的なシナリオに例えることができます：
あなたがプールの中央に石を投げ入れた時に広がる波紋のように、開始点から同心円状に探索範囲が広がっていきます。
または：
あなたが新しい街に引っ越してきたとき、まず自宅の周りを探索し、その後少し離れた場所を探索し、徐々に遠くへと範囲を広げていくのと同じです。
2. 幅優先探索の視覚的イメージ
幅優先探索の進み方を視覚的に説明します。
2.1 グラフでの探索
以下のようなグラフを考えてみましょう：
1
/ \
2 3
/ \ \
4 5 6
ノード1から探索を始めた場合、BFSは以下の順序で探索します：
- ノード1（レベル0）
- ノード2, 3（レベル1）
- ノード4, 5, 6（レベル2）
これを視覚的に表現すると：
レベル0: [1]
/ \
レベル1: [2] [3]
/ \ \
レベル2: [4] [5] [6]
探索は波が広がるように、レベルごとに進みます。
2.2 迷路での探索
迷路を例に考えてみましょう。以下はシンプルな迷路です：
S . # . .
. . # . .
. . . . .
# # . # #
. . . . G
（S: スタート, G: ゴール, #: 壁, .: 通路）
スタート地点からBFSで探索すると、以下のように移動可能なセルを「波紋」のように探索していきます：
最初の状態：
S . # . .
. . # . .
. . . . .
# # . # #
. . . . G
1歩目（距離1）：
S 1 # . .
1 . # . .
. . . . .
# # . # #
. . . . G
2歩目（距離2）：
S 1 # . .
1 2 # . .
2 . . . .
# # . # #
. . . . G
このように、スタートから等距離にあるセルを順に探索していきます。
3. 幅優先探索の主な用途
BFSは様々な場面で活用されています：
- 最短経路問題: 二点間の最短経路を見つける
- 連結成分の検出: グラフ内の連結した要素を見つける
- レベル順探索: ツリー構造をレベル（深さ）順に探索する
- ネットワーク分析: ソーシャルネットワークの「友達の友達」を見つけるなど
- パズル解法: 特定の状態から目標状態に到達する最小手数を求める
4. 幅優先探索のアルゴリズム
BFSのアルゴリズムを疑似コードで表現します：
function BFS(graph, startNode):
// すべてのノードを「未訪問」としてマーク
let visited = set()
// キューを初期化し、開始ノードを追加
let queue = new Queue()
queue.enqueue(startNode)
visited.add(startNode)
while queue is not empty:
// キューから次のノードを取得
let currentNode = queue.dequeue()
// 必要に応じて処理を行う（例：表示する）
process(currentNode)
// 隣接するすべてのノードを確認
for each neighbor of currentNode:
// まだ訪問していないノードのみキューに追加
if neighbor is not in visited:
visited.add(neighbor)
queue.enqueue(neighbor)
5. Pythonでの実装例
5.1 基本的な実装
まず、シンプルなグラフでのBFSの実装例を示します：
from collections import deque
def bfs(graph, start_node):
# 訪問済みノードを記録するセット
visited = set([start_node])
# キューを初期化し、開始ノードを追加
queue = deque([start_node])
while queue:
# キューから次のノードを取得
current_node = queue.popleft()
# ノードを処理（ここでは表示するだけ）
print(current_node, end=' ')
# 隣接ノードを探索
for neighbor in graph[current_node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# 使用例
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print("BFSの訪問順序:")
bfs(graph, 'A') # 出力: A B C D E F
5.2 キューの可視化
BFSでのキューの変化を確認するために、各ステップでキューの状態を表示する拡張バージョン：
from collections import deque
def bfs_with_queue_visualization(graph, start_node):
visited = set([start_node])
queue = deque([start_node])
step = 0
print(f"ステップ {step}: キュー = {list(queue)}, 現在のノード = まだ処理なし")
while queue:
step += 1
current_node = queue.popleft()
print(f"ステップ {step}: キュー = {list(queue)}, 現在のノード = {current_node}")
for neighbor in graph[current_node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
print(f" - ノード {neighbor} をキューに追加")
print("探索完了")
# 使用例
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
bfs_with_queue_visualization(graph, 'A')
6. 問題1: 迷路の最短経路
それでは、迷路の最短経路問題を解説します。
6.1 問題の定義
問題文:
NxMのマス目からなる迷路があります。'S'はスタート地点、'G'はゴール地点、'#'は壁、'.'は通路を表します。上下左右の4方向に移動できるとき、スタートからゴールまでの最短経路のステップ数を求めてください。ゴールに到達できない場合は-1を出力してください。
入力例:
5 6
S.#...
..#...
..#...
..#...
.....G
出力例:
10
6.2 問題の考え方
迷路の最短経路問題は、BFSが最も適したアルゴリズムの一つです。なぜなら：
- すべての移動（上下左右への1マス移動）のコストが同じ（=1）であるため
- BFSは同じコストの場合、最短経路を保証するため
- 迷路はグラフとして表現でき、各セルはノード、隣接するセル間の移動はエッジとみなせるため
6.3 解法のステップ
- スタート地点'S'とゴール地点'G'の座標を見つける
- スタート地点からBFSを開始する
- 各マスまでの最短距離を記録する2次元配列を用意する
- 上下左右の4方向に移動可能かをチェックし、可能ならキューに追加する
- ゴールに到達したら、その距離を返す
- キューが空になってもゴールに到達しなかった場合は-1を返す
6.4 視覚的な解説
例えば、以下の迷路を考えてみましょう：
S.#...
..#...
..#...
..#...
.....G
BFSの進行過程は以下のようになります（数字は開始地点からの距離）：
S1#... → S1#... → S1#... → ... → S1#456
2.#... 23#... 234... 23#456
..#... ..#... 56#... 56#567
..#... ..#... ..#... 89#78G
.....G .....G .....G 9ABCDE
最終的に、ゴール'G'までの距離は10（上図ではアルファベットA=10）となります。
6.5 実装（Python）
from collections import deque
def solve_maze(maze, n, m):
# スタートとゴールの位置を探す
start_r, start_c = 0, 0
goal_r, goal_c = 0, 0
for i in range(n):
for j in range(m):
if maze[i][j] == 'S':
start_r, start_c = i, j
elif maze[i][j] == 'G':
goal_r, goal_c = i, j
# 距離を管理する2次元配列（-1は未訪問）
distance = [[-1 for _ in range(m)] for _ in range(n)]
distance[start_r][start_c] = 0
# 移動方向（上下左右）
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
# BFSの実装
queue = deque([(start_r, start_c)])
while queue:
r, c = queue.popleft()
# ゴールに到達した場合
if r == goal_r and c == goal_c:
return distance[r][c]
# 4方向を探索
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
# 範囲内で、壁でなく、未訪問の場合
if 0 <= nr < n and 0 <= nc < m and maze[nr][nc] != '#' and distance[nr][nc] == -1:
distance[nr][nc] = distance[r][c] + 1
queue.append((nr, nc))
# ゴールに到達できない場合
return -1
# 入力を受け取る
n, m = map(int, input().split())
maze = []
for _ in range(n):
maze.append(input())
# 結果を出力
print(solve_maze(maze, n, m))
6.6 コードの詳細解説
スタートとゴールの位置を特定
# スタートとゴールの位置を探す
start_r, start_c = 0, 0
goal_r, goal_c = 0, 0
for i in range(n):
for j in range(m):
if maze[i][j] == 'S':
start_r, start_c = i, j
elif maze[i][j] == 'G':
goal_r, goal_c = i, j
迷路内のすべてのマスをチェックして、'S'と'G'の位置を見つけます。
距離配列の初期化
# 距離を管理する2次元配列（-1は未訪問）
distance = [[-1 for _ in range(m)] for _ in range(n)]
distance[start_r][start_c] = 0
各マスまでの距離を記録する2次元配列を作成します。初期値は-1（未訪問）で、スタート地点の距離は0とします。
移動方向の定義
# 移動方向（上下左右）
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
上下左右の4方向への移動を表す配列です。(dr[i], dc[i])のペアで移動方向を表します。
BFSのメインループ
queue = deque([(start_r, start_c)])
while queue:
r, c = queue.popleft()
# ゴールに到達した場合
if r == goal_r and c == goal_c:
return distance[r][c]
キューを初期化し、スタート地点を追加します。キューから座標を取り出し、ゴールに到達したかチェックします。
隣接マスの探索
# 4方向を探索
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
# 範囲内で、壁でなく、未訪問の場合
if 0 <= nr < n and 0 <= nc < m and maze[nr][nc] != '#' and distance[nr][nc] == -1:
distance[nr][nc] = distance[r][c] + 1
queue.append((nr, nc))
現在の位置から上下左右の4方向をチェックします。新しい位置が以下の条件を満たす場合にキューに追加します：
- 迷路の範囲内である
- 壁('#')ではない
- まだ訪問していない（distance[nr][nc] == -1）
有効な新しい位置の距離を更新し（現在の距離+1）、キューに追加します。
6.7 視覚化つき実装
BFSの進行過程を視覚的に確認するバージョン：
from collections import deque
import time
def solve_maze_with_visualization(maze, n, m):
# スタートとゴールの位置を探す
start_r, start_c = 0, 0
goal_r, goal_c = 0, 0
for i in range(n):
for j in range(m):
if maze[i][j] == 'S':
start_r, start_c = i, j
elif maze[i][j] == 'G':
goal_r, goal_c = i, j
# 距離を管理する2次元配列
distance = [[-1 for _ in range(m)] for _ in range(n)]
distance[start_r][start_c] = 0
# 移動方向（上下左右）
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
# BFSの実装
queue = deque([(start_r, start_c)])
# 視覚化用のマップ
visual_map = [list(row) for row in maze]
print("【初期状態】")
print_maze(visual_map, n, m)
time.sleep(1)
step = 0
while queue:
step += 1
r, c = queue.popleft()
print(f"\n【ステップ {step}】")
print(f"現在位置: ({r}, {c})")
# ゴールに到達した場合
if r == goal_r and c == goal_c:
print("\n【探索完了】")
print(f"スタートからゴールまでの最短距離: {distance[r][c]}")
return distance[r][c]
# 4方向を探索
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
# 範囲内で、壁でなく、未訪問の場合
if 0 <= nr < n and 0 <= nc < m and maze[nr][nc] != '#' and distance[nr][nc] == -1:
distance[nr][nc] = distance[r][c] + 1
queue.append((nr, nc))
# 視覚化マップを更新
if visual_map[nr][nc] not in ['S', 'G']:
visual_map[nr][nc] = str(distance[nr][nc] % 10) # 1桁の数字で表示
# 現在の状態を表示
print_maze(visual_map, n, m)
print(f"キューの状態: {list(queue)}")
time.sleep(0.5)
# ゴールに到達できない場合
print("\n【探索失敗】")
print("ゴールに到達できませんでした。")
return -1
def print_maze(maze, n, m):
"""迷路を見やすく表示する関数"""
print(" " + " ".join([str(i % 10) for i in range(m)])) # 列番号
for i, row in enumerate(maze):
print(f"{i % 10} " + " ".join(row)) # 行番号と迷路データ
# 使用例
maze = [
"S.#...",
"..#...",
"..#...",
"..#...",
".....G"
]
n, m = 5, 6
solve_maze_with_visualization(maze, n, m)
6.8 学習のポイント
この問題から学べる重要なポイント：
- キューの使い方: dequeを使用して効率的にBFSを実装
- 訪問管理: distanceの2次元配列で訪問状態と距離を管理
- 境界チェック: 迷路の範囲内かどうかの確認
- 条件分岐: 壁や訪問済みかどうかのチェック
- 座標の操作: dr, dcの配列を使って簡潔に4方向への移動を表現
- 終了条件: ゴールに到達したか、または全ての到達可能なセルを訪問したか
7. 応用と発展
BFSの基本を理解した後、以下のような応用や発展が考えられます：
- 優先度付きBFS: 通常のキューではなく優先度付きキューを使用
- 双方向BFS: スタートとゴールの両方から同時に探索
- 多始点BFS: 複数の開始点から同時にBFSを行う
- 状態空間の探索: 迷路だけでなく、様々な「状態」をノードとするグラフでのBFS
- 0-1 BFS: 辺の重みが0または1の場合の効率的なBFS
8. まとめ
幅優先探索（BFS）は、グラフや迷路などの探索において非常に重要なアルゴリズムです。以下がBFSの主なポイントです：
- 特徴: 開始点からの距離が近いノードから順に探索
- データ構造: キュー（Queue）を使用
- 強み: 最短経路を見つけることができる（辺の重みが等しい場合）
- 実装のコツ: 訪問管理と境界チェックが重要
- 応用: 最短経路問題、連結成分の検出、レベル順探索など
迷路の最短経路問題は、BFSの基本を理解するのに最適な問題です。実際のコードを通して、キューの使い方、訪問状態の管理、探索の進め方などのBFSの核心部分を学ぶことができます。
BFSはコンピュータサイエンスの基本的なアルゴリズムの一つであり、様々な問題解決に応用できる強力なツールです。基本を理解し、さまざまな問題に適用してみることで、アルゴリズム的思考力を高めることができるでしょう。