幅優先探索と深さ優先探索
キューと再帰の違いから、グラフの訪問順と戻り方を学びます。
説明
グラフ探索は、接続をたどって到達できる頂点を調べる処理です。幅優先探索は近い頂点から順に調べるためキューを使います。深さ優先探索は一つの枝を奥へ進み、行き止まりで戻って別の枝を調べます。閉路がある場合は訪問済みの管理が必要です。
AからB・Cへ分岐し、BからD、CからD・E、DからAへ戻るグラフを使います。幅優先では待ち行列と距離、深さ優先では入口と出口の履歴を表示します。到達しないFも残し、開始点から探索できる範囲を確認します。
1接続と初期状態
辞書の各リストは、その頂点から進める接続先です。列挙順はB・Cなど記載した順で固定します。
from collections import deque待ち行列; graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D', 'E'], 'D': ['A'], 'E': [], 'F': []}グラフ; queue = deque(['A']); distance = {'A': 0}開始点だけを登録; graph接続先一覧A→B→D→Aという閉路があります。Fは接続されていません。距離は重みのない辺を何本通るかで数え、開始点Aは0とします。
2Aの隣をキューへ入れる
先頭Aを取り出し、初めて見つけたBとCを距離1で記録してキュー末尾へ入れます。
current = queue.popleft()先頭Aを取り出す; distance['B'] = distance[current]+1; distance['C'] = distance[current]+1初発見時に距離を記録; queue.extend(['B', 'C'])順に待機させる; current, list(queue), distance処理頂点・待機列・距離待ち行列はB・Cです。Bを処理した後もCが先に待っているため、Bの奥の頂点よりCを先に処理します。
3Bの奥にDを追加
Bを取り出しDを距離2で追加します。DはCより後ろに並びます。
current = queue.popleft()Bを取得; distance['D'] = distance[current]+1Dの距離は2; queue.append('D')Dを末尾へ; current, list(queue), distance更新した待機状態待ち行列はC・Dです。キューは先に入ったものを先に取り出すため、距離1のCを残して距離2のDへ先に進むことがありません。
4同じDを二度入れない
Cの接続先Dは既にdistanceにあります。新しいEだけを記録して追加します。
current = queue.popleft()Cを取得; new = [v for v in graph[current] if v not in distance]未発見だけを抽出; distance.update({v: distance[current]+1 for v in new})距離を記録; queue.extend(new)新規頂点を追加; current, new, list(queue), distance重複を除いた待機状態新規頂点はEだけ、待機列はD・Eです。訪問済みをキューへ入れる時点で記録すると、複数の親から同じ頂点を二重登録することを防げます。
5閉路と到達不能
DからのAは既に発見済み、Eには出る辺がありません。残りを取り出した後、距離表にない頂点を表示します。
current = queue.popleft()Dを取得; [v for v in graph[current] if v not in distance]Aは発見済み; current = queue.popleft(); graph[current]Eの出口は空; list(queue), [v for v in graph if v not in distance], distance終了状態と到達不能点待機列は空、到達しなかった頂点はFです。D→AでAを再登録しないので閉路でも終了します。全ての辺の重みが同じ場合、初めて記録した距離が最少の辺数です。
6深さ優先で入口と出口を記録
今度は一つの接続先の探索が終わるまで待ってから次へ進みます。enterは到着、leaveは全ての接続先を調べ終えて呼び出し元へ戻る位置です。
def dfs(vertex, seen, trace):現在地・訪問済み・履歴
seen.add(vertex)到着時に記録
trace.append(('enter', vertex))入口を記録
for neighbor in graph[vertex]:接続先を順に選ぶ
if neighbor not in seen: dfs(neighbor, seen, trace)未訪問の枝を最後まで探索
trace.append(('leave', vertex))呼び出し元へ戻る再帰呼び出しは処理中の頂点を呼び出し履歴に保持します。訪問済みのAへ戻る辺は再帰しません。リストの順番を変えれば訪問順も変わります。
7Bの枝から戻ってCへ進む
Aから深さ優先で探索します。Bの先Dを先に調べ、DからB、BからAへ戻ってからCへ進みます。
seen = set(); trace = []記録を初期化; dfs('A', seen, trace)Aから深さ優先; print(*trace, sep='\n')入口・出口の全履歴入口の順序はA・B・D・C・Eです。DとBのleaveがCのenterより前にあり、枝から戻ったことが分かります。幅優先のA・B・C・D・Eとは順序が異なります。
8訪問順と到達集合
幅優先と深さ優先が到達した頂点集合を照合します。訪問の順序は違っても、この開始点から到達できる範囲は同じです。
[v for kind, v in trace if kind == 'enter']深さ優先の訪問順, sorted(seen), sorted(distance)両方式の到達点, set(distance) == seen到達集合の一致到達集合はA・B・C・D・Eで一致します。深さ優先の最初の経路は、辺数が最小とは限りません。目的が到達確認か、最少辺数か、枝から戻る順序かによって探索方法を選びます。
まとめ
幅優先探索はキューで近い頂点から処理し、重みが同じ辺の最少本数を求めます。
深さ優先探索は枝を奥まで調べて戻ります。入口と出口を記録すると戻りの順序が分かります。
発見済みの管理で閉路や重複を処理し、到達不能な頂点は別に残します。
操作履歴と解説を振り返れます。
Python 3
from collections import deque; graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D', 'E'], 'D': ['A'], 'E': [], 'F': []}; queue = deque(['A']); distance = {'A': 0}; graph{'A': ['B', 'C'], 'B': ['D'], 'C': ['D', 'E'], 'D': ['A'], 'E': [], 'F': []}current = queue.popleft(); distance['B'] = distance[current]+1; distance['C'] = distance[current]+1; queue.extend(['B', 'C']); current, list(queue), distance('A', ['B', 'C'], {'A': 0, 'B': 1, 'C': 1})current = queue.popleft(); distance['D'] = distance[current]+1; queue.append('D'); current, list(queue), distance('B', ['C', 'D'], {'A': 0, 'B': 1, 'C': 1, 'D': 2})current = queue.popleft(); new = [v for v in graph[current] if v not in distance]; distance.update({v: distance[current]+1 for v in new}); queue.extend(new); current, new, list(queue), distance('C', ['E'], ['D', 'E'], {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2})current = queue.popleft(); [v for v in graph[current] if v not in distance]; current = queue.popleft(); graph[current]; list(queue), [v for v in graph if v not in distance], distance[]
[]
([], ['F'], {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2})def dfs(vertex, seen, trace):
seen.add(vertex)
trace.append(('enter', vertex))
for neighbor in graph[vertex]:
if neighbor not in seen: dfs(neighbor, seen, trace)
trace.append(('leave', vertex))seen = set(); trace = []; dfs('A', seen, trace); print(*trace, sep='\n')('enter', 'A')
('enter', 'B')
('enter', 'D')
('leave', 'D')
('leave', 'B')
('enter', 'C')
('enter', 'E')
('leave', 'E')
('leave', 'C')
('leave', 'A')[v for kind, v in trace if kind == 'enter'], sorted(seen), sorted(distance), set(distance) == seen(['A', 'B', 'D', 'C', 'E'], ['A', 'B', 'C', 'D', 'E'], ['A', 'B', 'C', 'D', 'E'], True)
演習完了