Depth-first search (DFS)

Why it costs this much

Each vertex is entered once, and each edge is examined once.

Code

def dfs(graph, u, seen):
    seen.add(u)
    for v in graph[u]:              # each edge is examined once overall
        if v not in seen:
            dfs(graph, v, seen)     # each vertex is entered once

Common pitfalls

Recursion depth can reach V, which exceeds Python's default recursion limit (about 1000) on long chains. Use an explicit stack for deep graphs.

Operation by operation

Depth-first search. Adjacency list. Space is the recursion depth plus the visited set. Recursive DFS can overflow the stack on deep graphs. Use an explicit stack.