Pythonの深さ優先探索DFS
DFSは再帰または明示的なスタックを利用します。
Pythonの深さ優先探索DFSとは？
DFSは再帰または明示的なスタックを利用します。
戻る前に1つの経路を深く探索します。
どのような場面で使う？
- アルゴリズムとデータ構造を理解する。
- 各ステップと境界ケースを確認する。
- 実行時間とメモリ使用量を比較する。
Pythonの深さ優先探索DFSのビジュアライザー
O(V+E)再生またはステップを使って、比較とデータ移動を順に確認できます。
サンプルコード
main.py
graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
def depth_first(node, visited=None):
visited = visited or set()
visited.add(node)
order = [node]
for neighbor in graph[node]:
if neighbor not in visited:
order.extend(depth_first(neighbor, visited))
return order
print(depth_first("A"))期待される出力
['A', 'B', 'D', 'C', 'E']仕組み
各頂点と辺を最大1回処理するためO(V+E)です。
値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。
練習問題
入力値と境界ケースを変更し、より大きなデータでも動作を確認してください。
- 空入力、1要素、重複値を試す。
- 各ステップの状態を表示する。
- 別の解法と性能を比較する。