BFS/DFS
1. BFS（幅優先探索）とDFS（深さ優先探索）の概要
Graphを探索するアルゴリズム
簡単な問題だと問題で与えられたGraphに対してそのまま適用すれば良いが，難しい問題になると与えられたデータからGraphを作成して，それに対してDFS/BFSをやることもある
例：状態をノードとみなしたGraphを作成し，DFS/BFSで状態遷移をやる とか
2. BFS（Breadth First Search）の実装
(1) 概要
queue（キュー）を使うのが王道．
Queueモジュールはマルチスレッド対応してる分遅いので、競プロ環境(シングルスレッド)ではcollections.dequeを使うと良い
派生として，01BFS（枝長が0 or 1のみの最短経路問題）がある．
(2) コード例
https://scrapbox.io/files/63eb559e2c54df001cd381a1.png
上の木に対するBFS
code:python
from collections import deque
2, 8, 9, 2, 10, 11, 3, 12, 13, 3, 14, 15, q = deque(1) # 点1のみキューに入った状態で初期化 route = []
while q:
v = q.popleft()
route.append(v)
for u in adjv: # 現在の点から隣接する点u q.append(u) # 未探索の点はキューに追加
print(*route)
# 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
3. DFS（Depth First Search）の実装
(1) 概要
再帰関数でやるのと，stackを使って実装する二通りの方法がある(再帰関数も内部的にはstackで実装されてるので本質は同じ)．問題に応じて使い分けられると嬉しい．
再帰の場合はPyPy苦手なのでPythonを使う
派生として，反復深化DFS(ID-DFS)とかがある
(2) コード例
https://scrapbox.io/files/63eb559e2c54df001cd381a1.png
上の木に対するDFS
code: python
import sys
sys.setrecursionlimit(1000000)
def dfs(v):
route.append(v)
dfs(u)
2, 8, 9, 2, 10, 11, 3, 12, 13, 3, 14, 15, route = []
dfs(1)
print(*route)
# 1 2 4 8 9 5 10 11 3 6 12 13 7 14 15
再帰回数の上限は，sys.setrecursionlimitで設定．デフォルト値が小さい（2000回）ので，必要に応じて設定する．
(3) dequeによるDFS
BFSの append を appendleft に変更するだけでDFSに変更可能．探索順序に注意．
code: python
from collections import deque
2, 8, 9, 2, 10, 11, 3, 12, 13, 3, 14, 15, q = deque(1) # 点1のみキューに入った状態で初期化 route = []
while q:
v = q.popleft()
route.append(v)
for u in adjv: # 現在の点から隣接する点u q.appendleft(u) # 未探索の点はキューに追加
print(*route)
# 1 3 7 15 14 6 13 12 2 5 11 10 4 9 8
(4) 帰りがけ順の処理を非再帰DFSで実装
実装例：ハミルトニアン路（全ての点を1度ずつ通る道）
code: python
from collections import deque
# 1 -- 2 -- 4
# | |
# ---- 3 -- 5
n = len(adj) # 全点数
for s in adj:
on_path = set()
q = deque(~s, s) # 始点（帰り用／行き用）がキューに入った状態で初期化 on_path.add(s)
while q:
v = q.pop()
if v >= 0: # 行き用の点の場合
on_path.add(v)
if len(on_path) == n: # 全点通るパスが見つかったら
path = deque()
while q:
w = q.pop()
if w < 0: # 帰り用の点のみ，pathの先頭に追加
path.appendleft(~w) # 帰り用から行き用に変換
exit(print(*path, sep='->'))
for u in adjv: # 現在の点から隣接する点u if u not in on_path:
q.append(~u) # 帰り用．-ではなく~にするとu = 0にも対応可能
q.append(u) # 行き用
else: # 帰り用の点の場合
on_path.remove(~v) # 帰り用から行き用に変換
print('There is no Hamiltonian Path.')
# 出力：4->2->1->3->5
応用例
経路
探索
連結性
なんかを列挙
BFSの練習
DFSの練習