BFSとは？幅優先探索のアルゴリズムとデータ構造の操作方法
BFSは「幅優先探索」とも呼ばれ、グラフ探索アルゴリズムの一つです。グラフ探索アルゴリズムとは、ある始点から出発して、目的地に到達するまでの経路を探索するためのアルゴリズムです。BFSは、同じ深さのノードをすべて探索し、次の深さのノードに進む前に、現在の深さのノードをすべて探索するアルゴリズムです。
BFSアルゴリズムは、キューというデータ構造を使用します。始点をキューに入れ、次にその始点に隣接するすべてのノードをキューに入れます。そして、キューの先頭からノードを取り出し、そのノードに隣接するすべてのノードをキューに入れます。この過程を目的地が見つかるか、すべてのノードが探索されるまで繰り返します。
BFSアルゴリズムは、最短経路問題を解決するために使用されます。また、迷路を解く、トポロジカルソート、最大フロー問題、グラフの同型性テストなどにも使用されます。
幅優先探索のアルゴリズムの例
以下は、BFSアルゴリズムの例です。始点から目的地までの最短経路を探索する場合、BFSアルゴリズムを使用することができます。
“`
1. キューに始点を入れる。
2. キューが空になるまで、以下の手順を繰り返す。
1. キューの先頭からノードを取り出す。
2. 取り出したノードが目的地かどうかを調べる。
– 目的地であれば、終了。
3. 取り出したノードに隣接するノードをすべてキューに入れる。
4. キューが空になるまで、2.を繰り返す。
“`
アルゴリズムの実装例
以下は、PythonでBFSアルゴリズムを実装する例です。グラフは隣接リストで表されています。
“`python
def bfs(graph, start, goal):
queue = [(start, [start])]
while queue:
(node, path) = queue.pop(0)
for next_node in graph[node] – set(path):
if next_node == goal:
return path + [next_node]
else:
queue.append((next_node, path + [next_node]))
“`
以上のように、BFSアルゴリズムは、幅優先探索と呼ばれるグラフ探索アルゴリズムの一つです。キューを使って、同じ深さのノードをすべて探索し、次の深さのノードに進む前に、現在の深さのノードをすべて探索するアルゴリズムです。実装例も示しましたので、ぜひ参考にしてみてください。
参考記事
合わせて読みたい
【Google Chrome】右クリックで翻訳がでなくなった時の対策方法の決定版