DFS

Problem¶

List node's values in a graph starting from start node using DFS.

Key trick¶

Great for structure problems: connected components, cycle detection, topological sort.

Trap¶

Recursion depth on deep graphs; forgetting visited causes infinite loops.

Why is it interesting?¶

Reachability, backtracking, components.

Python solution¶

def dfs_recursive(graph, start):
    visited = set()
    res = []

    def go(node):
        visited.add(node)
        res.append(node)
        for nei in graph.get(node, []):
            if nei not in visited:
                go(nei)

    go(start)
    return res


def dfs_iterative(graph, start):
    if not graph:
        return []

    res = []
    visited = {start}
    stack = [start]

    while stack:
        node = stack.pop()

        res.append(node)

        # Reverse neighbors to match the recursive traversal res.
        for nei in reversed(graph.get(node, [])):
            if nei not in visited:
                visited.add(node)
                stack.append(nei)

    return res