深さ優先探索
ツリーの深さ優先探索とグラフの深さ優先探索は区別するべき
後者は既に訪問済みの頂点を再度訪問しないようにする必要がある
再帰呼び出しで実装するのが手軽だが関数呼び出しのコストが問題になることがある
code:python
def visit(v):
for c in children
v
:
parent
c
= v
visit(c)
visit(root)
code:python
stack =
root
while stack:
v = stack.pop()
for c in children
v
:
parent
c
= v
stack.append(c)
DFS