Quiz
Warm-up from Data Structures: you represented a graph as a dictionary mapping each node to a list of its neighbors. What is that representation called?
Depth-first search
Graphs model anything connected to anything: social networks, package dependencies, links between pages, states of a game. Nearly every graph question — is X reachable from Y, how many separate clusters exist, is there a cycle — starts with a traversal: visiting every node once by following edges. DFS is the first of the two traversals every engineer carries, and the one you get almost for free from unit 5.
DFS explores a graph by going as deep as possible before backing up: visit a node, then fully explore its first neighbor (and that neighbor's first neighbor...) before ever touching the second.
That is exactly the recursion you mastered in unit 5. The call stack does the "remember where to back up to" work for free.
One graph-specific danger: graphs can have cycles (E points back to B below). Without a visited set, DFS would loop forever. So the rule is: mark a node visited the moment you reach it, and never enter a visited node again.
DFS visits every reachable node once, and checks every edge once: O(V + E) time.
Code exercise · python
Run this. The graph is a dictionary adjacency list. Watch the order: DFS finishes A's first branch (B, then D) completely before starting the second branch (C, E). The E → B edge is a cycle, and the visited set absorbs it.
Quiz
Delete the visited set from dfs and run it on that same graph. What happens?
Code exercise · python
Your turn, a classic: count connected components. The network below is undirected (edges listed both ways). Loop over every node, and each time you find one you have never visited, DFS floods its whole component and you count 1.