Depth-First Search (DFS) on Graphs

DFS goes deep before backtracking—great for cycles, connected components, and topological sort on DAGs.

Why this shows up in the real world

Maps & routing, social networks, and dependency systems are modeled as graphs—vertices are places or tasks, edges are roads or prerequisites.

Core idea (explained for students)

Recursive go(u) or explicit stack. Mark visited on entry. For trees, parent pointer avoids revisiting parent undirected edge.

Try this in Python

def dfs(adj: list[list[int]], start: int) -> list[int]:
    seen = set()
    order: list[int] = []

    def go(u: int) -> None:
        seen.add(u)
        order.append(u)
        for v in adj[u]:
            if v not in seen:
                go(v)

    go(start)
    return order


print(dfs([[1, 2], [0], [0]], 0))

Common mistakes

• Stack overflow on deep graphs in Python—use iterative DFS.
• Missing visited on undirected graphs.

Key takeaways

• Three-color DFS detects cycles in directed graphs.
• Discovery/finish times underpin Tarjan and Kosaraju.