Python3で深さ優先探索と幅優先探索と双方向探索の実装

幅優先探索と深さ優先探索をPythonでシンプルに実装してみました。
今回は以下のようなグラフを例にノードb（Start）からノードg（End）への探索を実装してみます。
![スクリーンショット 2019-10-24 0.27.36.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/391115/3ad8a19c-9439-d433-a2e2-0040384c497d.png)
##入力
以下のようなDictionary形式で各ノードと隣接するノードを表すことにします。

```python:search.py
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に既出のノードを記録して無限ループを回避している）

##実装

```python:search.py
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にしてループさせる
【一致する】→終了

##実装

```python:search.py
# 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)となり幅優先探索よりも少なくて済む。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/391115/1589a92d-1e0b-bfca-a9a5-7d50fd6e8c60.png)
こちらの記事を参考にした。
https://qiita.com/guicho271828/items/cf1e7fcb98b1f074eacb

##考え方
Start(b)由来かEnd(g)由来か識別するためのFlagを格納するQueueのClassを作る。
あとは幅優先探索とほぼ同じ考え方
Queueから要素取り出し
【自分の探索で未出】→Queueにその隣接ノードに隣接するノードを入れ、Queueの最初の要素をStartにしてループさせる
【自分の探索で既出】→Pass
【反対の探索で既出】→終了

（それぞれの探索で既出のノードを格納するmark_dictを設定した）

##実装

```python:search.py
# 双方向探索のためのフラグ付き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')
```