幅優先探索

幅優先探索（Breadth First Search）

幅優先探索（BFS）は、グラフや木構造のデータ構造を探索するためのアルゴリズムの一つです。根ノードから開始し、隣接するノードを全て探索してから、次の階層のノードへと進むため、「横型探索」とも呼ばれます。

アルゴリズム

幅優先探索は、以下の手順で実行されます。

1. 初期化: 探索を開始する根ノードをキューに追加します。
2. 探索: キューからノードを取り出し、そのノードが探索対象であるかをチェックします。もし探索対象であれば、探索は終了します。
3. 展開: 対象ノードでなければ、そのノードの子ノードを全てキューに追加します。これにより、次の探索対象がキューに格納されます。
4. 反復: キューが空になるまで、ステップ2と3を繰り返します。もしキューが空になった場合、グラフ内の全てのノードを探索したにも関わらず、対象が見つからなかったことを意味します。

擬似コード

function 幅優先[探索]
Q ← 空のキュー
v に訪問済みの印を付ける
v を Q に追加
while Q が空ではない do
v ← Q から取り出す
v を処理する
for each v に接続している頂点 i do
if i が未訪問 then
i に訪問済みの印を付ける
i を Q に追加

アルゴリズムの特徴

時間計算量

幅優先探索の最悪時間計算量は、O(|E|)です。ここで|E|はグラフ内の辺の数を表します。これは、探索対象のノードを発見するために、最悪の場合、グラフの全ての辺を辿る必要があるためです。

空間計算量

幅優先探索の空間計算量は、O(|V|)またはO(B^M)と表せます。|V|はグラフ内のノードの数を表します。また、Bは枝分かれの最大数、Mは木の最長経路の長さを表します。

幅優先探索は、訪問した全てのノードを記録する必要があるため、探索空間が広くなるとメモリ消費量が大きくなるというデメリットがあります。

完全性

幅優先探索は完全なアルゴリズムです。つまり、解が存在する場合、必ず解を見つけ出すことができます。

最適性

幅優先探索は、重みなしグラフにおいて、開始ノードから終了ノードへの最短経路を見つけることができます。しかし、重み付きグラフの場合は、必ずしも最短経路を見つけることができるとは限りません。重み付きグラフの最短経路を求めるには、ダイクストラ法などの他のアルゴリズムを使う必要があります。

幅優先探索の応用

幅優先探索は、グラフ理論における様々な問題を解決するために利用できます。

連結成分の検出: グラフ内の連結成分を特定できます。幅優先探索で到達可能なノードの集合が、初期ノードを含む連結成分となります。
最小全域木: 重みなしグラフの最小全域木を求めることができます。
最短経路: 重みなしグラフの単一始点最短経路問題を解くことができます。
二部グラフ判定: グラフが二部グラフかどうかを判定できます。幅優先探索の同じ段階で発見されたノード間に辺が存在する場合、そのグラフは二部グラフではありません。

実装例

幅優先探索は、様々なプログラミング言語で実装できます。

Python

python
def bfs(graph, start):
visited = set()
queue = [start]
visited.add(start)
while queue:
vertex = queue.pop(0)
print(vertex, end=" ")
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)

例

graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}

bfs(graph, 'A') # 出力: A B C D E F

関数型言語での実装

参照透過な関数型言語では、遅延評価と再帰を使用することで、より簡潔に幅優先探索を実装できます。

まとめ

幅優先探索は、グラフ探索の基本的なアルゴリズムであり、様々な分野で応用されています。その特徴を理解することで、より効率的なプログラムを開発することができます。

関連項目

深さ優先探索

外部リンク

深さ優先探索と幅優先探索 - 高校数学の美しい物語
C++ Boost Graph Library: Breadth-First Search
Depth First and Breadth First Search: Explanation and Code

もう一度検索