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

8.1 BFSアルゴリズムの動作原理

幅優先探索 (Breadth-First Search, BFS)はグラフの探索またはトラバースアルゴリズムで、開始頂点から始めて、次のレベルの頂点に移動する前に、現在のレベルのすべての隣接頂点を探索します。

アルゴリズムのステップ:

1. 選択した開始頂点から始め、これをキューに入れます。
2. キューが空でない限り、次の操作を行います:
   • キューの先頭から頂点を取り出し、訪問済みとしてマークします。
   • 未訪問の隣接頂点に対して、これをキューに追加します。
3. 開始頂点から到達可能なすべての頂点が訪問されるまで、ステップ2を繰り返します。

ビジュアライゼーション:

時間計算量:

O(V + E)、ここでVは頂点の数、Eは辺の数です。

グラフの各ノードと各エッジは一度だけ訪問されます。

空間計算量:

O(V)、キューと訪問状態のための配列を利用します。

8.2 キューを使用したBFSの実装

幅優先探索はデータ構造のキューを使用してうまく実装できます。

キューを使用したBFSの実装:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
            
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # ノードの処理
            
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    queue.append(neighbor)
            
# 使用例:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
bfs(graph, 'A')

8.3 両方向幅優先探索

BFSはゲームでよく使われ、複雑な地形の中で二点間の最短経路を見つける必要がある場合に利用されます。このような問題は、二つの頂点間のグラフでの経路探索問題に変換しやすいです。グラフのエッジは、地図上のすべての歩ける道です。

しかし、もっと早く経路を見つけるために、通常両端から探します。このために両方向BFSが用いられます。

作業の原理

両方向幅優先探索 (Bidirectional BFS) はBFSの最適化バージョンで、始点からの探索と終点からの探索の2つの並列トラバースを実行します。両トラバースが合流するまで続けることで、クラシックなBFSに比べてチェックされる頂点とエッジの数を大幅に削減します。

アルゴリズムのステップ:

• 2つのキューを初期化: 始点からのトラバース用と終点からのもの。
• 両方向で訪問済みの頂点を追跡するために2つの訪問済み頂点のセットを初期化。
• 2つのキューを交互にグラフをトラバースします。
• 各ステップで訪問済み頂点のセットが交差するか確認します。交差が見つかれば、道は存在します。
• 交差ノードが見つかるか、キューが空になるまでプロセスは続きます。

時間計算量

最良の場合: O(2 * (V + E)) = O(V + E)、Vは頂点の数、Eは辺の数です。

両方向BFSは通常、単一パスBFSよりも少ない頂点をトラバースし、特に大きなグラフで効果を発揮します。

空間計算量:

O(V)。2つのキューと2つの訪問済み頂点セットを保存します。

両方向BFSの実装例

例がとても長いので、三倍くらい長いアルゴリズムがあるため、ここでは省略します。必要な時には、自分で書けるようになるでしょう。

8.4 BFSを使用して解かれる問題の例

BFSを使用して解決する古典的な問題の例:

1. 無向グラフでの最短経路探索:

BFSは、無向グラフでの始点から終点までの最短経路（最小エッジ数）を見つけるために使用されます。

応用:

• ナビゲーションシステムでの点間最短経路の探索。
• ネットワーク解析でのデータ伝送の最短経路の発見。

2. グラフの連結性の確認:

グラフが連結しているか、すなわち任意の2つの頂点間に経路が存在するかを確認します。

応用:

• ネットワーク解析でのネットワークの連結性の確認。
• ソーシャルネットワーク分析でのユーザーグループの連結性の確認。

3. 迷路生成:

指定された特性を持つランダム迷路を生成するためにBFSを使用します。

応用:

• ゲームアプリでの迷路の生成。
• ロボット工学でのナビゲーションアルゴリズムのテスト。

4. 木構造での幅優先探索:

BFSは木をトラバースして、各レベルでアクションを実行するために使用されます（例: 各レベルのすべてのノードを出力）。

応用:

• データをレベルごとに表示する必要があるデータビジュアライゼーションの課題。
• 階層ごとにアクションを実行する必要があるプランニングの課題。

5. グラフの二部性の確認:

グラフが二部グラフであるか、すなわち頂点を二つの集合に分けて、辺が異なる集合の頂点間にのみ存在するかを確認します。

応用:

• グラフ理論でのグラフの二部性の確認。
• グラフを二色で塗り分けできるかどうかを確認するグラフ着色の課題。