幅優先探索と深さ優先探索をPythonでシンプルに実装してみました。
今回は以下のようなグラフを例にノードb（Start）からノードg（End）への探索を実装してみます。
入力
以下のようなDictionary形式で各ノードと隣接するノードを表すことにします。
graph = {
'a': ['c'],
'b': ['c','f'],
'c': ['a','b','d'],
'd': ['e','f'],
'e': ['d'],
'f': ['b','d','g'],
'g': ['f']
}
深さ優先探索(Depth-First Search)
考え方
Start(b)の隣接ノードそれぞれについてEnd(g)と一致しているかチェック
【一致しない】→Startの隣接ノードをStartにして探索の関数を再帰する
【一致する】→終了
（mark_dictに既出のノードを記録して無限ループを回避している）
実装
import sys
# 深さ優先探索
def DFS(graph,start,end,mark_dict):
mark_dict[start] = True
for target in graph[start]:
if target == end:
print('Exist')
sys.exit()
elif target not in mark_dict:
mark_dict[target] = True
DFS(graph,target,end,mark_dict)
DFS(graph,'b','g',{})
幅優先探索(Breadth-First Search)
考え方
Start(b)の隣接ノードがEnd(g)と一致しているかチェック
【一致しない】→Queueにその隣接ノードに隣接するノードを入れ、Queueの最初の要素をStartにしてループさせる
【一致する】→終了
実装
# queueの実装
class Queue:
def __init__(self):
self.queue = []
# 先頭にデータを追加
def add(self,x):
self.queue.append(x)
# 最後のデータを削除
def remove(self):
del self.queue[0]
# 最後のデータを返す
def peek(self):
return self.queue[0]
# 空かどうか確認
def is_empty(self):
return len(self.queue) == 0
# 幅優先探索
def BFS(graph,start,end):
mark_dict = {}
queue = Queue()
queue.add(start)
while queue.is_empty() == False:
target = queue.peek()
queue.remove()
if target not in mark_dict:
mark_dict[target] = True
if target != end:
for elem in graph[target]:
queue.add(elem)
else:
print('Exist')
sys.exit()
BFS(graph,'b','g')
双方向探索
幅優先探索を元のノードと目的地のノードの二ヶ所から同時に行う探索方法。
なぜこの探索方法が早いのかについての議論を書いておく。
各ノードがk個の隣接ノードを持っているグラフだと仮定する。
・幅優先探索だと、深さdの時点でk^dのノードを調べる必要がある。
・双方向探索だと、2つの探索がおよそ深さd/2の時点で衝突する。探索ノード数は元のノードからがk^(d/2)、最終ノードからk^(d/2)となり、合計ノード数は2*k^(d/2)となり幅優先探索よりも少なくて済む。
こちらの記事を参考にした。
https://qiita.com/guicho271828/items/cf1e7fcb98b1f074eacb
考え方
Start(b)由来かEnd(g)由来か識別するためのFlagを格納するQueueのClassを作る。
あとは幅優先探索とほぼ同じ考え方
Queueから要素取り出し
【自分の探索で未出】→Queueにその隣接ノードに隣接するノードを入れ、Queueの最初の要素をStartにしてループさせる
【自分の探索で既出】→Pass
【反対の探索で既出】→終了
（それぞれの探索で既出のノードを格納するmark_dictを設定した）
実装
# 双方向探索のためのフラグ付きqueueの実装
class FlagQueue:
def __init__(self):
self.queue = []
# 先頭にデータを追加
def add(self,x,flag):
self.queue.append([x,flag])
# 最後のデータを削除
def remove(self):
del self.queue[0]
# 最後のデータを返す
def peek(self):
return self.queue[0]
# queueをprint
def get_queue(self):
print(self.queue)
# 空かどうか確認
def is_empty(self):
return len(self.queue) == 0
# 双方向探索
def BidirectionalSearch(graph,start,end):
mark_dict = {0: {},1: {}}
queue = FlagQueue()
queue.add(start,0)
queue.add(end,1)
while queue.is_empty() == False:
target = queue.peek()
queue.remove()
# 'target'が反対側のdictionaryで既出
if target[0] in mark_dict[1-target[1]]:
print('Exist')
sys.exit()
# 'target'が自分側のdictionaryで未出
elif target[0] not in mark_dict[target[1]]:
mark_dict[target[1]][target[0]] = True
for elem in graph[target[0]]:
queue.add(elem,target[1])
BidirectionalSearch(graph,'b','g')