深さ優先探索

ツリーの深さ優先探索とグラフの深さ優先探索は区別するべき 後者は既に訪問済みの頂点を再度訪問しないようにする必要がある 再帰呼び出しで実装するのが手軽だが関数呼び出しのコストが問題になることがある

python

    def visit(v):
        for c in children[v]:
            parent[c] = v
            visit(c)

    visit(root)

python

    stack = [root]
    while stack:
        v = stack.pop()
        for c in children[v]:
            parent[c] = v
            stack.append(c)

DFS