グラフの幅優先探索（BFS）:コード例と解析

BFSの概要 BFSは、キューを使用してグラフ内のノードを探索するアルゴリズムです。以下にBFSの基本的な手順を示します。

スタートノードをキューに追加します。
キューが空になるまで、以下の手順を繰り返します。
- キューからノードを取り出します。
- 取り出したノードを処理します（例: ノードの値を表示する）。
- 取り出したノードに隣接する未探索のノードをキューに追加します。
キューが空になったら、探索が終了です。

BFSの具体例以下に、BFSの具体例として、単純なグラフの探索を行うコードを示します。

from collections import deque
def bfs(graph, start_node):
    visited = set()
    queue = deque([start_node])
    while queue:
        node = queue.popleft()
        print(node)  # ノードの値を表示する
        if node not in visited:
            visited.add(node)
            neighbors = graph[node]
            queue.extend(neighbors)
# グラフの定義
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
# BFSの実行
bfs(graph, 'A')

このコードでは、'A'を始点として、グラフ内のノードをBFSで探索しています。各ノードの値が表示されます。この例では、出力は'A', 'B', 'C', 'D', 'E', 'F'の順になります。

BFSの応用例 BFSは、グラフ探索においてさまざまな応用があります。以下にいくつかの応用例を紹介します。

最短経路の探索: グラフ内の2つのノード間の最短経路を見つけるためにBFSを使用できます。
迷路の解決: 迷路内の最短経路を見つけるためにBFSを使用できます。
グラフの連結成分の探索: グラフ内の連結成分を見つけるためにBFSを使用できます。