幅優先探索とは？

# 幅優先探索（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. ノード1（レベル0）
2. ノード2, 3（レベル1）
3. ノード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の実装例を示します：

```python
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でのキューの変化を確認するために、各ステップでキューの状態を表示する拡張バージョン：

```python
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マス移動）のコストが同じ（=1）であるため
2. BFSは同じコストの場合、最短経路を保証するため
3. 迷路はグラフとして表現でき、各セルはノード、隣接するセル間の移動はエッジとみなせるため

### 6.3 解法のステップ

1. スタート地点'S'とゴール地点'G'の座標を見つける
2. スタート地点からBFSを開始する
3. 各マスまでの最短距離を記録する2次元配列を用意する
4. 上下左右の4方向に移動可能かをチェックし、可能ならキューに追加する
5. ゴールに到達したら、その距離を返す
6. キューが空になってもゴールに到達しなかった場合は-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）

```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 コードの詳細解説

#### スタートとゴールの位置を特定
```python
# スタートとゴールの位置を探す
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'の位置を見つけます。

#### 距離配列の初期化
```python
# 距離を管理する2次元配列（-1は未訪問）
distance = [[-1 for _ in range(m)] for _ in range(n)]
distance[start_r][start_c] = 0
```
各マスまでの距離を記録する2次元配列を作成します。初期値は-1（未訪問）で、スタート地点の距離は0とします。

#### 移動方向の定義
```python
# 移動方向（上下左右）
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
```
上下左右の4方向への移動を表す配列です。(dr[i], dc[i])のペアで移動方向を表します。

#### BFSのメインループ
```python
queue = deque([(start_r, start_c)])

while queue:
    r, c = queue.popleft()
    
    # ゴールに到達した場合
    if r == goal_r and c == goal_c:
        return distance[r][c]
```
キューを初期化し、スタート地点を追加します。キューから座標を取り出し、ゴールに到達したかチェックします。

#### 隣接マスの探索
```python
# 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方向をチェックします。新しい位置が以下の条件を満たす場合にキューに追加します：
1. 迷路の範囲内である
2. 壁('#')ではない
3. まだ訪問していない（distance[nr][nc] == -1）

有効な新しい位置の距離を更新し（現在の距離+1）、キューに追加します。

### 6.7 視覚化つき実装

BFSの進行過程を視覚的に確認するバージョン：

```python
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 学習のポイント

この問題から学べる重要なポイント：

1. **キューの使い方**: dequeを使用して効率的にBFSを実装
2. **訪問管理**: distanceの2次元配列で訪問状態と距離を管理
3. **境界チェック**: 迷路の範囲内かどうかの確認
4. **条件分岐**: 壁や訪問済みかどうかのチェック
5. **座標の操作**: dr, dcの配列を使って簡潔に4方向への移動を表現
6. **終了条件**: ゴールに到達したか、または全ての到達可能なセルを訪問したか

## 7. 応用と発展

BFSの基本を理解した後、以下のような応用や発展が考えられます：

1. **優先度付きBFS**: 通常のキューではなく優先度付きキューを使用
2. **双方向BFS**: スタートとゴールの両方から同時に探索
3. **多始点BFS**: 複数の開始点から同時にBFSを行う
4. **状態空間の探索**: 迷路だけでなく、様々な「状態」をノードとするグラフでのBFS
5. **0-1 BFS**: 辺の重みが0または1の場合の効率的なBFS

## 8. まとめ

幅優先探索（BFS）は、グラフや迷路などの探索において非常に重要なアルゴリズムです。以下がBFSの主なポイントです：

- **特徴**: 開始点からの距離が近いノードから順に探索
- **データ構造**: キュー（Queue）を使用
- **強み**: 最短経路を見つけることができる（辺の重みが等しい場合）
- **実装のコツ**: 訪問管理と境界チェックが重要
- **応用**: 最短経路問題、連結成分の検出、レベル順探索など

迷路の最短経路問題は、BFSの基本を理解するのに最適な問題です。実際のコードを通して、キューの使い方、訪問状態の管理、探索の進め方などのBFSの核心部分を学ぶことができます。

BFSはコンピュータサイエンスの基本的なアルゴリズムの一つであり、様々な問題解決に応用できる強力なツールです。基本を理解し、さまざまな問題に適用してみることで、アルゴリズム的思考力を高めることができるでしょう。