【超基本】初心者に贈るアルゴリズム論 ～深さ優先探索～
スポンサーリンク
深さ優先探索とは
深さ優先探索はグラフの探索方法の1つです．
できる限り奥まで探索して，行き止まりになったら分岐点まで戻って探索を繰り返す方法です．
例えば，あなたが部屋でスマホをなくしたとします．
ある隣の部屋からなるべく奥の部屋まで探して，見つからなければ最初の部屋に戻り，別の隣の部屋からなるべく奥の部屋まで探す方法が深さ優先探索です．
一方で，今いる部屋に隣り合っている部屋を全部探してから，それら部屋の奥の部屋をすべて探し，それでも見つからなければさらに奥の部屋...と探していくのが幅優先探索です．
それではコードを見てみましょう．
実装例
# 隣接行列 am = [[0, 1, 0, 1, 1, 0], # s(0) [1, 0, 1, 0, 0, 0], # 1 [0, 1, 0, 0, 0, 0], # 2 [1, 0, 0, 0, 1, 1], # 3 [1, 0, 0, 1, 0, 1], # 4 [0, 0, 0, 1, 1, 0]] # 5 def DFS(am): visit = [0] * len(am) # 訪問済 or 未訪問 stack = [] # s(0)を訪問 visit[0] = 1 adj = am[0] for i in range(0, len(adj)): if adj[i] == 1: stack.append([0, i]) print('S=' + str(stack) + '\n') while stack: edge = stack.pop(-1) # スタックから辺(x,y)を取り出す[f:id:talosta:20190711002329p:plain] y = edge[1] if visit[y] == 0: # 未訪問 visit[y] = 1 adj = am[y] # 頂点yに接続する辺の終点のリスト for i in range(0, len(adj)): if adj[i] == 1: # 隣接している stack.append([y, i]) print('edge=' + str(edge)) print('adj(y)=' + str([i for i, x in enumerate(adj) if x == 1])) print('S=' + str(stack) + '\n') DFS(am)
出力
S=[[0, 1], [0, 3], [0, 4]] edge=[0, 4] adj(y)=[0, 3, 5] S=[[0, 1], [0, 3], [4, 0], [4, 3], [4, 5]] edge=[4, 5] adj(y)=[3, 4] S=[[0, 1], [0, 3], [4, 0], [4, 3], [5, 3], [5, 4]] edge=[5, 3] adj(y)=[0, 4, 5] S=[[0, 1], [0, 3], [4, 0], [4, 3], [3, 0], [3, 4], [3, 5]] edge=[0, 1] adj(y)=[0, 2] S=[[1, 0], [1, 2]] edge=[1, 2] adj(y)=[1] S=[[1, 0], [2, 1]]
上から順番に見ていきましょう．
下図のような無向グラフがあります．
これを隣接行列であらわすと，
となります．
隣接行列とは，グラフの頂点と頂点の隣接関係を表す正方行列です．
頂点uと頂点vが隣り合っているとき(u,v)成分は1，隣り合っていないときは0になります．
例えば，頂点1と頂点2は隣り合っているので(1,2)成分は1，頂点1と頂点3は隣り合っていないので(1,3)成分は0です．
これをプログラム上で表現するには，二次元配列を使って，
am = [[0, 1, 0, 1, 1, 0], # s(0)
[1, 0, 1, 0, 0, 0], # 1
[0, 1, 0, 0, 0, 0], # 2
[1, 0, 0, 0, 1, 1], # 3
[1, 0, 0, 1, 0, 1], # 4
[0, 0, 0, 1, 1, 0]] # 5と書きます．
visit = [0] * len(am) # 訪問済 or 未訪問 stack = []
visitは頂点に訪問したかどうかを保存する配列です．
頂点の数だけ0で初期化します．
stackはスタックです．
深さ優先探索では一番奥まで探索したら1つ前の頂点に戻り，そこからまたできる限り深く探索します．
戻る頂点は一番最近に訪問された頂点になる必要があるため，先入れ後出しのスタックを用います．
visit[0] = 1 adj = am[0] for i in range(0, len(adj)): if adj[i] == 1: stack.append([0, i]) print('S=' + str(stack) + '\n')
まず，始点sに訪問するので，visit[0]に1を入れます．
その後，始点に接続する辺をスタックに入れます．
while stack: edge = stack.pop(-1) # スタックから辺(x,y)を取り出す y = edge[1] if visit[y] == 0: # 未訪問 visit[y] = 1 adj = am[y] # 頂点yに接続する辺の終点のリスト for i in range(0, len(adj)): if adj[i] == 1: # 隣接している stack.append([y, i])
stackが空になるまでwhileループを回します．
stackが空になるとすべての頂点を調べたということなので終了します．
ループに入ると，まずはstackの末尾から辺(x,y)を取り出します．
その後，頂点yが未訪問であればvisitを1にして，頂点yから延びる辺をスタックに入れます．
実行すると以下のように動きます．
sを訪問，S={(s,1),(s,3),(s,4)}
4を訪問，S={(s,1),(s,3),(4,s),(4,3),(4,5)}
5を訪問，S={(s,1),(s,3),(4,s),(4,3),(5,3),(5,4)}
S={(s,1),(s,3),(4,s),(4,3),(5,3)}
3を訪問，S={(s,1),(s,3),(4,s),(4,3),(3,s),(3,4),(3,5)}
S={(s,1),(s,3),(4,s),(4,3),(3,s),(3,4)}
S={(s,1),(s,3),(4,s),(4,3),(3,s)}
S={(s,1),(s,3),(4,s),(4,3)}
S={(s,1),(s,3),(4,s)}
S={(s,1),(s,3)}
S={(s,1)}
1を訪問，S={(1,s),(1,2)}
2を訪問，S={(1,s),(2,1)}
S={(1,s)}
S={}
再帰を利用した深さ優先探索
こちらの方がシンプルでわかりやすいですね．
# 隣接行列 am = [[0, 1, 0, 1, 1, 0], # s(0) [1, 0, 1, 0, 0, 0], # 1 [0, 1, 0, 0, 0, 0], # 2 [1, 0, 0, 0, 1, 1], # 3 [1, 0, 0, 1, 0, 1], # 4 [0, 0, 0, 1, 1, 0]] # 5 visit = [0] * len(am) # 訪問済 or 未訪問 def DFS(u): visit[u] = 1 adj = am[u] for i in range(0, len(adj)): if adj[i] == 1 and visit[i] == 0: print('edge=' + str([u, i])) DFS(i) DFS(0)
出力
edge=[0, 1] edge=[1, 2] edge=[0, 3] edge=[3, 4] edge=[4, 5]
出力を図で表すと以下のようになります．
(ページ下部の参考文献を参考に作成)
DFS(s)
DFS(1)
DFS(2)
DFS(3)
DFS(4)
DFS(5)
参考
