幅優先探索について説明

幅優先探索(Breadth-First Search, BFS)はグラフや木構造などのデータ構造を探索するためのアルゴリズムです。

BFSは、最も近い頂点から順に探索します。

以下はPythonによるBFSの例です。

from collections import deque

def BFS(graph, start):
    # graphは隣接リストで表現されたグラフ、startは探索を開始する頂点
    visited = set() # 訪れた頂点を保存するset
    queue = deque([start]) # キュー
    while queue:
        vertex = queue.popleft() # キューから取り出す
        if vertex not in visited:
            visited.add(vertex) # 訪れたことを記録
            queue.extend(graph[vertex] - visited) # 訪れていない頂点をキューに追加
    return visited

使用例は下記に記載

graph = {0: set([1, 2]), 1: set([0, 3]), 2: set([0, 4]), 3: set([1]), 4: set([2])}
result = BFS(graph, 0)
print(result) # output: {0, 1, 2, 3, 4}

上記の例では、隣接リストで表現されたグラフを引数に、頂点0からBFSを実行し、訪れた頂点をsetで返しています。

BFSは、最短経路問題や、グラフの接続性の判定などにも使用されます。