深さ優先探索
#Algorithm #Graph #DFS
Abstract辺をたどって行けるところまで行くやつ.
$ O(|V| + |E|)timeのグラフ走査のアルゴリズム. 非再帰版の深さ優先探索 (Depth First Search: DFS) のテンプレートを書いた.
Explanation
TODO 書く.
Implementation再帰で書く方が簡潔ではある.
キューで実装する幅優先探索との対応を考えて, スタックを使って非再帰で実装した.
Input
グラフ (頂点は0-indexed) の隣接リスト E
DFSの始点 s
Output
DFSの先行順序 preorder
DFSの後行順序 postorder
DFS木での親 parent
DFS木における深さ depth
Time complexity
$ O(|V| + |E|)time.
code:python
def dfs(E, s):
N = len(E)
preorder = -1 * N # a dfs preordering of each vertex
postorder = -1 * N # a dfs postordering of each vertex
parent = -1 * N # parent of each vertex in the dfs search tree
depth = -1 * N # the depth of each vertex
stack = (s, -1, 0) # (vertex, parent, status)
pre_num = 0 # current preordering
post_num = 0 # current preordering
d = 0 # current depth
while stack:
v, p, st = stack.pop()
if st == 0 and preorderv < 0: # visited v for the first time
preorderv = pre_num; parentv = p; depthv = d
pre_num += 1
n_children = 0
for u in Ev:
if preorderu >= 0: continue
if n_children == 0:
stack += (v, p, 2), (u, v, 0)
n_children += 1
else:
stack += (v, p, 1), (u, v, 0)
n_children += 1
if n_children == 0: # v is a leaf
postorderv = post_num
post_num += 1
d -= 1
else:
d += 1
elif st == 0 and preorderv >= 0: # the edge (v, p) is a back edge
d -= 1
elif st == 1: # now searching
d += 1
else: # search finished
postorderv = post_num
post_num += 1
d -= 1
return preorder, postorder, parent, depth
Verification
特になし. 他のところでも使いまわしているけど, そちらでもVerifyできているのでおそらく大丈夫.
References
非再帰で書きたくて何か見ながら書いたはず. けどメモするの忘れた.