何を頂点と辺にするか決める
駅と路線、Webページとリンク、仕事と依存関係などは、グラフとして表せます。ただし、同じ対象でも辺の向きや重みの意味は設計によって変わります。「リンクがある」と「相互に移動できる」は同じではありません。まず、頂点が何を表し、どちらへ移動でき、何を最短にしたいかを定義します。
到達できるかだけを調べる問題と、辺の本数が最小の経路を探す問題と、所要時間の合計を最小にする問題は異なります。探索手法を選ぶ前に、目的と入力の条件を言葉にしましょう。存在しない頂点、孤立した頂点、自己ループ、同じ辺の重複も、入力として扱うか決めておきます。
BFSは、近い層から広げる
幅優先探索BFSでは、通常はキューを使って始点から近い層の頂点を先に処理します。すべての辺の移動コストが等しい場合、始点から通る辺の本数が最小の距離を求められます。頂点を初めてキューへ入れるときに発見済みとして記録すれば、同じ頂点を何度も追加するのを防げます。
例えば、AからBとCへ辺があり、CからBへも辺があるとします。AからのBの距離は1です。Cを後で調べてBを見つけても、Bを新しく追加し直す必要はありません。距離と前の頂点を記録しておけば、到達の判定に加えて、発見した経路を後から復元できます。
from collections import deque
def distances(graph, start):
distance = {start: 0}
queue = deque([start])
while queue:
u = queue.popleft()
for v in graph.get(u, []):
if v not in distance:
distance[v] = distance[u] + 1
queue.append(v)
return distanceDFSは、深く進んで戻る
深さ優先探索DFSは、一つの枝を深くたどってから別の枝へ戻る進め方です。明示的なスタックや再帰で実装できます。到達性やグラフの構造を調べる用途に役立ちますが、最初に見つけた経路が、辺の本数の最小経路であるとは限りません。訪問済みの管理を忘れると、サイクルを巡って処理が終わらないこともあります。
再帰版では、グラフが深いと呼び出しスタックの制限にも注意が必要です。また、有向グラフのサイクル判定では、単に以前見た頂点かどうかだけではなく、現在の探索経路にいるかを区別する方法などを使います。目的ごとに、記録すべき状態が変わります。
重みがあるときと、計算量の限界
AからBへコスト5の辺、AからCへコスト1の辺、CからBへコスト1の辺があるとします。BFSは1本の辺でBに到達できますが、最小コストはCを通る2です。辺の本数の最小化と重み合計の最小化を区別し、非負の重みならDijkstra法などを検討します。負の重みを許す場合は、さらに条件に合う方法が必要です。
隣接リストで各頂点と辺を必要な回数だけ扱う基本的なBFSやDFSは、O(V+E)と説明できます。隣接行列で全列を毎回調べる実装では、同じ説明をそのまま当てはめられません。表現、入力の大きさ、到達範囲、補助メモリまで含めて、計算量を確認しましょう。