Graphs and depth-first search

That representation is an adjacency list.

A dictionary mapping each node to a list of its neighbors is the default graph representation in interviews, for two reasons.

It uses O(V + E) space, storing one entry per node plus one entry per edge, rather than the O(V²) of a full matrix. On a sparse graph, which most real graphs are, that is an enormous difference.

Iterating a node's neighbors is also cheap, since the list holds exactly the neighbors and nothing else. A matrix would require scanning all V cells of a row to find them.

This whole unit works on adjacency lists and on grids, which are adjacency lists in disguise, since a cell's neighbors can be computed instead of stored.

Depth-first search

Graphs model anything connected to anything: social networks, package dependencies, links between pages, states of a game.

Nearly every graph question starts with a traversal, meaning visiting every node once by following edges. Whether X is reachable from Y, how many separate clusters exist, whether there is a cycle, all of them are traversals with a small amount of bookkeeping.

DFS is the first of the two traversals every engineer carries, and the one you get almost for free from unit 5.

DFS explores by going as deep as possible before backing up. It visits a node, then fully explores its first neighbor and that neighbor's first neighbor, before ever touching the second.

That is exactly the recursion from unit 5. The call stack does the remembering, holding the path back to the root so there is no bookkeeping to write.

One graph-specific danger is that graphs can have cycles, and without a visited set DFS would loop forever. The rule is to mark a node visited the moment you reach it and never enter a visited node again.

The cost is easy to justify. Every reachable node is visited once and every edge is examined once, so DFS is O(V + E) time, with O(V) space for the visited set and the stack.

DFS on an adjacency list

The graph is a dictionary, and the visited set absorbs the cycle.

graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["E"],
    "D": [],
    "E": ["B"],
}

def dfs(node, visited):
    if node in visited:
        return
    visited.add(node)
    print("visiting", node)
    for neighbor in graph[node]:
        dfs(neighbor, visited)

dfs("A", set())

Output

visiting A
visiting B
visiting D
visiting C
visiting E

The order is the thing to read. DFS finishes A's first branch completely, reaching B and then D, before it ever starts the second branch of C and E.

That is why B and D print before C, even though C is A's immediate neighbor and D is two steps away. Depth beats proximity.

The if node in visited: return guard at the top is the cycle defense, and putting it inside the function rather than at the call site means only one place has to be right.

E's neighbor list contains B, and by the time E is reached B is already visited, so the call returns immediately. The cycle costs one wasted call rather than an infinite loop.

Passing visited down means every call shares one set, which is the same discipline as the memo in lesson 5-3. A fresh set per call would defeat the whole mechanism.

The recursion never terminates, and Python raises RecursionError.

E's neighbor list contains B, so the walk goes A, B, D, back up, then C, E, and from E straight back into B.

From there it repeats forever. B leads to D, D returns, E leads to B, and nothing in the code notices it has been here before.

It is not an infinite loop that hangs, though. Each revisit is a fresh function call, so the stack grows until the depth limit from lesson 5-1 stops it, which happens in a fraction of a second.

Trees are the special case that makes this easy to forget. A tree has no cycles by definition, so plain recursion is safe there and many people first meet DFS on trees.

On graphs, visited is not optional. It is the one line that separates a traversal from a crash, and interviewers watch for whether you add it without prompting.

Counting connected components

Each fresh DFS floods one whole island, so the number of starts is the number of components.

def count_components(graph):
    visited = set()

    def dfs(node):
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                dfs(neighbor)

    count = 0
    for node in graph:
        if node not in visited:
            visited.add(node)
            dfs(node)
            count += 1
    return count

network = {1: [2], 2: [1], 3: [4], 4: [3, 5], 5: [4], 6: []}
print(count_components(network))

Output

3

The graph is undirected, which here means every edge is listed in both directions. Node 4 appears in 3's list and node 3 appears in 4's, and that redundancy is what makes an undirected graph work as an adjacency list.

The outer loop is the new part. DFS alone only reaches one component, so every node needs a chance to start a traversal, and the if node not in visited check makes sure a node inside an already-flooded component does not start a second count.

This version marks nodes before recursing rather than at the top of dfs, which is why the outer loop also marks the starting node. Both styles work, and mixing them is where the bugs come from.

The three components are {1, 2}, {3, 4, 5}, and {6}, and the isolated node 6 counts as a component of its own.

The total cost is still O(V + E), since the outer loop touches each node once and DFS visits each node and edge once across all the components combined.