DFS（深さ優先探索）とBFS（幅優先探索）を、別々のコードとして覚える必要はない。
探索の本体を共通にして、次に調べる頂点を入れておくデータ構造だけを差し替えると、どちらも実装できる。
スタックとキューは、取り出す順番が違う
どちらもデータを一時的に入れておく容器だが、取り出す順番が異なる。Pythonの標準ライブラリには、それぞれに対応するクラスがある。
| データ構造 | 取り出す順番 | Pythonのクラス |
|---|---|---|
| スタック | 最後に入れたものから取り出す。後入れ先出し（LIFO） | LifoQueue |
| キュー | 最初に入れたものから取り出す。先入れ先出し（FIFO） | Queue |
探索では、この違いが「新しく見つけた頂点を先に調べるか」「先に見つけて待たせている頂点から調べるか」という違いになる。
データ構造だけで切り替えるPythonコード
今回は、次の木をAから探索する。辺は親から子へ向かうものとする。
A
/ \
B C
/ \ / \
D E F G
LifoQueueとQueueは、どちらもput()で追加し、get()で取り出し、empty()で空かどうかを確認できる。探索側は、容器の種類を判定する必要がない。
以下がコード全体。
from queue import LifoQueue, Queue
def traverse(
graph: dict[str, list[str]],
start: str,
frontier_type: type[Queue[str]],
) -> list[str]:
"""開始頂点から到達可能な頂点を、訪問順に返す。"""
frontier = frontier_type()
frontier.put(start)
visited: set[str] = set()
order: list[str] = []
while not frontier.empty():
node = frontier.get()
# 同じ頂点が複数回入っていても、処理するのは最初の1回だけ。
if node in visited:
continue
# 「追加したとき」ではなく「取り出したとき」に訪問済みにする。
visited.add(node)
order.append(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
frontier.put(neighbor)
return order
if __name__ == "__main__":
graph = {
"A": ["B", "C"],
"B": ["D", "E"],
"C": ["F", "G"],
"D": [],
"E": [],
"F": [],
"G": [],
}
# 変えるのは、候補を管理するデータ構造だけ。
print("DFS:", " -> ".join(traverse(graph, "A", LifoQueue)))
print("BFS:", " -> ".join(traverse(graph, "A", Queue)))
実行結果は次のとおり。
DFS: A -> C -> G -> F -> B -> E -> D
BFS: A -> B -> C -> D -> E -> F -> G
変更したのは、第3引数のLifoQueueとQueueだけ。
traverse()の中には、DFSかBFSかを判定する条件分岐はない。隣接頂点を追加する順番も、訪問済みを管理する処理も共通。
なぜ、これだけで探索方法が変わるのか
スタックなら、新しい候補を優先する
Aを処理すると、B、Cの順に追加される。
スタックでは最後に入れたものから取り出すので、次はC。CからF、Gを追加すると、今度はGが先に取り出される。
容器の右側から取り出すものとして書くと、次のようになる。
Aを処理した後 [B, C]
Cを処理した後 [B, F, G]
Gを処理した後 [B, F]
Fを処理した後 [B]
Bは先に見つかっているが、C側の探索が優先された。
新しく見つけた候補が、待っている候補より先に処理される。この順番によって、枝を深くたどる動きになる。
なお、このコードで右側から探索するのは、隣接頂点を左から右へ追加しているため。「左から探索すること」がDFSの条件ではない。
キューなら、待っている候補を優先する
キューでは最初に入れたものから取り出すので、Aの次はB。
BからD、Eが見つかっても、すでに待っているCより後ろに並ぶ。
今度は容器の左側から取り出す。
Aを処理した後 [B, C]
Bを処理した後 [C, D, E]
Cを処理した後 [D, E, F, G]
新しく見つけた候補は、待っている候補を追い越さない。この順番によって、浅い層から順に探索が進む。
一般のグラフでも、BFSは始点からの最短距離、つまり必要な辺数が少ない頂点から訪問する。重みなしグラフの最短経路探索に使われるのは、この性質があるため。DFSには、最初にたどった経路が最短になる保証はない。
ただし、今回の関数が返すのは訪問順であり、経路そのものではない。
重要なのは、取り出したときに訪問済みにすること
共通化のポイントは、次の部分。
node = frontier.get()
if node in visited:
continue
visited.add(node)
このコードでは、候補を容器に追加しただけでは、訪問済みにしない。実際に取り出したときに記録する。
BFS専用の実装では、容器に追加する時点で訪問済みにする書き方も一般的。しかし、その実装のキューだけをスタックに変えると、一般のグラフでは正しいDFSにならない場合がある。後から深い経路を通って到達するはずの頂点を、浅い頂点の隣接先として早々に確定してしまうため。
今回の実装では、「候補に入っている」と「訪問済み」を区別することで、この問題を避けている。
同じ頂点が候補として複数回追加されることはあるが、2回目以降に取り出されたものはcontinueで無視。循環があっても、同じ頂点の隣接先を何度も展開することはない。
計算量と、この共通実装のトレードオフ
頂点数をV、辺数をEとします。集合・辞書の操作を平均O(1)として考えると、本コードの時間計算量はDFS・BFSともにO(V + E)
各頂点の隣接リストを調べるのは1回だけ。候補の重複があっても、追加回数の合計は辺数に比例する範囲に収まる。
一方、このコードの補助メモリ上限は、どちらもO(V + E)。 訪問済み集合と結果にO(V)、重複を含む候補の保持に最大O(E)を使う。取り出し時に訪問済みを判定する実装では、候補の重複によって必要なメモリが増える点に注意が必要。
また、この例は1スレッドで動かしている。QueueとLifoQueueは同期機構を備えていますが、empty()による確認とget()を組み合わせた処理を、そのまま複数スレッドで共有してよいわけではない。
まとめ
今回の探索関数が行うのは、候補を取り出し、未訪問なら処理し、隣接する頂点を候補に追加することだけ。
探索順序を決めているのは、関数内の条件分岐ではなく、渡されたデータ構造。
新しい候補を優先するスタックならDFS。待っている候補を優先するキューならBFS。
2つのコードを丸暗記するより、1つの探索処理と、2つの取り出し方として理解すると、違いが見通しやすくなる。