Pythonの幅優先探索BFS
BFSはキューを使い、近い隣接頂点から訪問します。
Pythonの幅優先探索BFSとは？
BFSはキューを使い、近い隣接頂点から訪問します。
グラフを階層ごとに探索します。
どのような場面で使う？
- アルゴリズムとデータ構造を理解する。
- 各ステップと境界ケースを確認する。
- 実行時間とメモリ使用量を比較する。
Pythonの幅優先探索BFSのビジュアライザー
O(V+E)再生またはステップを使って、比較とデータ移動を順に確認できます。
サンプルコード
main.py
from collections import deque
graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
queue = deque(["A"])
visited = {"A"}
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
print(order)期待される出力
['A', 'B', 'C', 'D', 'E']仕組み
visitedで再訪を防ぎ、時間O(V+E)、メモリO(V)です。
値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。
練習問題
入力値と境界ケースを変更し、より大きなデータでも動作を確認してください。
- 空入力、1要素、重複値を試す。
- 各ステップの状態を表示する。
- 別の解法と性能を比較する。