【アルゴリズム】BFS(幅優先探索)

はじめに

こんにちは。アメリカに住みながら独学でエンジニアを目指しているTairaです。
現在、Leetcodeでコーディング面接対策を始める前に重要そうなアルゴリズムをピックアップして勉強しています。
本日はBFS(幅優先探索)について記事にしたいと思います。

Breadth First Search（BFS）とは？

BFSは、グラフやツリーの探索アルゴリズムの1つで、起点から「近い順」に探索を進めていく手法です。

探索の流れは以下の通りです：

1. スタートノードから始める

2. その隣接ノードすべてを先に探索

3. 次に、その隣接ノードの隣接ノード…と進んでいく

---

どんな場面で使う？

BFSは「最短経路を求めたいとき」や「すべてのノードを漏れなく探索したいとき」に便利です。

代表的な使用場面

使用場面	説明
最短経路探索	迷路問題・地図アプリなどで、移動回数が最小のルートを見つける
ソーシャルネットワーク	「友達の友達」を検索する（距離が近い順）
ルーティング	ネットワーク経路検索やWebクローラー
状態探索	パズルやゲームの状態空間を探索する場合など

メリット・デメリット

項目	説明
メリット	最短経路が保証される（全ての辺の重みが同じ場合） 全ノードを公平に探索できる
デメリット	メモリ消費が大きい（キューと訪問済みリストを保持するため） 深さ優先探索（DFS）より非効率な場面もある（ゴールが深い場合など）

Pythonでの実装例（迷路の最短経路）

以下は、BFSを使って迷路の最短距離を探索する例です

from collections import deque

# 迷路（0は通れる, 1は壁）
maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [1, 1, 0, 1, 0],
    [0, 0, 0, 0, 0]
]

# スタートとゴール
start = (0, 0)
goal = (4, 4)

# 移動方向（上下左右）
directions = [(-1,0),(1,0),(0,-1),(0,1)]

def bfs(maze, start, goal):
    rows, cols = len(maze), len(maze[0])
    visited = [[False]*cols for _ in range(rows)]
    queue = deque()
    queue.append((start[0], start[1], 0))  # (x座標, y座標, 移動回数)

    while queue:
        x, y, dist = queue.popleft()
        if (x, y) == goal:
            return dist  # 最短距離が見つかった

        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols:
                if maze[nx][ny] == 0 and not visited[nx][ny]:
                    visited[nx][ny] = True
                    queue.append((nx, ny, dist + 1))
    
    return -1  # ゴールにたどり着けない

# 実行
shortest_path = bfs(maze, start, goal)
print("最短距離:", shortest_path)

まとめ

• BFSは「近い順」にノードを探索するアルゴリズム

• 最短経路を探する場面に適している

場合によってはDFS(深度優先探索)と使い分ける必要があるようです。まだDFSは学習していないので手を付け次第記事にしたいと思います