幅優先探索（BFS）とは？Pythonコードの具体例と解説付き！

具体例：迷路の探索

例えば、迷路の出口を見つけるためにBFSを使う場合を考えます。迷路は2次元のリストで表され、0は通れる道、1は壁、Eは出口を示します。

コード例（Python）

from collections import deque

def bfs(maze, start):
    rows, cols = len(maze), len(maze[0])
    queue = deque([start])
    visited = set()
    visited.add(start)
    
    # 上下左右の移動方向
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    while queue:
        x, y = queue.popleft()
        
        if maze[x][y] == 'E':
            return True
        
        for direction in directions:
            new_x, new_y = x + direction[0], y + direction[1]
            
            if (0 <= new_x < rows and 0 <= new_y < cols and
                (new_x, new_y) not in visited and maze[new_x][new_y] != 1):
                queue.append((new_x, new_y))
                visited.add((new_x, new_y))
    
    return False

# 使用例
maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 'E']
]
start = (0, 0)
result = bfs(maze, start)

if result:
    print("出口に到達しました！")
else:
    print("出口が見つかりませんでした。")

コードの解説

1. 必要なモジュールのインポート:

   from collections import deque
   

   deque を使ってキューを実装します。

2. 関数定義:

   def bfs(maze, start):
   

   bfs という名前の関数を定義しています。この関数は、迷路 maze の中で start から探索を開始し、出口を見つけることを目的としています。

3. 初期化:

   rows, cols = len(maze), len(maze[0])
   queue = deque([start])
   visited = set()
   visited.add(start)
   

   迷路の行数と列数を取得し、キュー queue に開始位置 start を追加します。また、訪問済みの場所を記録するためのセット visited を初期化し、開始位置を追加します。

4. 移動方向の定義:

   directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
   

   上下左右の移動方向を定義します。

5. キューの処理:

   while queue:
       x, y = queue.popleft()
       
       if maze[x][y] == 'E':
           return True
       
       for direction in directions:
           new_x, new_y = x + direction[0], y + direction[1]
           
           if (0 <= new_x < rows and 0 <= new_y < cols and
               (new_x, new_y) not in visited and maze[new_x][new_y] != 1):
               queue.append((new_x, new_y))
               visited.add((new_x, new_y))
   

   キューが空になるまでループを続けます。キューの先頭から位置を取り出し、その位置が出口 E であるかを確認します。出口であれば True を返します。各移動方向に対して、新しい位置 new_x, new_y を計算し、その位置が迷路の範囲内であり、訪問済みでなく、壁でない場合にキューに追加し、訪問済みとしてセットに追加します。

6. 出口が見つからない場合:

   return False
   

   すべての探索が終了しても出口が見つからない場合、False を返します。

7. 使用例:

   maze = [
       [0, 1, 0, 0, 0],
       [0, 1, 0, 1, 0],
       [0, 0, 0, 1, 0],
       [0, 1, 1, 1, 0],
       [0, 0, 0, 0, 'E']
   ]
   start = (0,