はじめに
どんな問題を解決するか
迷路の出口を探す、グラフに閉路があるか調べる、互いに依存するタスクを順番に並べる。これらはすべて、別の道を試す前に1つの道をできるだけ奥まで進む必要があります。それが深さ優先探索です。
身近なたとえ
深さ優先探索は、糸玉を持って洞窟を探検する方法です。1つのトンネルを行き止まりまで奥へ進みます。行き止まりでは糸をたどって直前の分かれ道に戻り、次のトンネルを試します。通ったトンネルには印を付け、二度と同じ所を通りません。
洞窟の探検からコードへ
visited.add(node)🧵 このトンネルを探検済みにするfor neighbor in graph[node]:🔀 ここから出る各トンネルを見るdepth_first(neighbor, visited)⬇️ まだ探検していない最初のトンネルの奥へ進むreturn order↩️ 行き止まり:糸をたどって戻るひと言でいうと
深さ優先探索(DFS)は、1つの枝をできるだけ深くたどってから戻ることでグラフを探索します。通常は再帰かスタックを使います。
重要なポイント
visited.add(node)はノードに印を付けるので、閉路があっても再帰が終わらなくなることはありません。for neighbor in graph[node]:は隣のノードを順に見ます。order.extend(depth_first(neighbor, visited))は、次の隣に進む前に、ある隣の下の枝全体を探索します。- B の枝を先に終えるので、結果は C より先に D を訪れます。
どんな場面で使う?
- 何らかの道を見つける、迷路やパズルをバックトラッキングで解く。
- 閉路の検出や、依存関係のあるタスクの並べ替え(トポロジカルソート)。
- グラフのすべての連結部分を探索する。
使わなくてよいとき
- 最短経路が必要な場合:深さ優先探索は長い道を先に見つけることがあります。幅優先探索を使います。
- 非常に深いグラフ:再帰が Python の上限に達することがあるので、明示的なスタックを使います。
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']
コードの解説
セットvisitedは訪問済みの頂点を記録し、同じ処理の繰り返しや、閉路のあるグラフでの無限ループを防ぎます。再帰呼び出しはそれぞれ未訪問の隣接頂点へ深く進むので、プログラムはA、B、Dを訪れてから戻ってC、Eを訪れます。関数の呼び出しスタックがアルゴリズムのスタックの役割を果たし、計算量はO(V + E)です。
値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。
発展問題
下のヒントにしたがってコードを書き換えてみましょう。自分で変えて結果を確かめると、コードを読むだけよりずっと深く理解できます。
- 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
- 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
- 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
よくある間違い
変更可能な初期値の引数を使う
visited=set() は別々の呼び出しの間で共有されてしまいます。
問題
def depth_first(node, visited=set()):
修正
def depth_first(node, visited=None):
visited = visited or set()
このレッスンを終えましたか?
学習済みにすると進み具合を記録できます。
進み具合はこのブラウザーに保存されています ログインすると、どのデバイスでも引き継げます。
チャレンジで練習する
このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。
- Count Islands Count groups of connected land cells in a grid. 中級
- Strongly Connected Components Count groups of nodes that can all reach each other. 難しい
- Longest Path in a DAG Find the heaviest path in a task dependency graph. 難しい