Patterns

Graphs, BFS, and DFS

A graph is a set of nodes plus a set of edges. Unlike the trees on the trees page, a graph may contain a cycle, and a node may be reachable by more than one path. That single difference changes the code: every serious walk needs a visited set, or you will follow a cycle forever. If you remember nothing else, remember the visited set.

This page uses adjacency lists. A dictionary maps each node to the list of nodes it can reach directly. For an undirected graph, add both directions when you build the list. For a directed graph, add only the direction the prompt allows. Building that representation is part of the solution. Do not leave it implicit.

Counting components with DFS

A connected component is a maximal set of nodes that can reach each other. Counting them is a depth-first search from every node that has not been visited yet. Each fresh start is a new component.

Original task: undirected hallways connect rooms. halls is a list of pairs. Return how many components the rooms form, including rooms listed in rooms that have no hallway.

def count_components(rooms: list[str], halls: list[tuple[str, str]]) -> int:
    neighbors: dict[str, list[str]] = {room: [] for room in rooms}
    for left, right in halls:
        neighbors[left].append(right)
        neighbors[right].append(left)

    seen: set[str] = set()

    def visit(room: str) -> None:
        seen.add(room)
        for nxt in neighbors[room]:
            if nxt not in seen:
                visit(nxt)

    components = 0
    for room in rooms:
        if room not in seen:
            visit(room)
            components += 1
    return components


assert count_components(["a", "b", "c", "d"], [("a", "b"), ("b", "c")]) == 2
assert count_components(["a"], []) == 1

Building the adjacency lists scans every hallway once and every room once. The search visits each room once and looks at each hallway a constant number of times. Time is linear in rooms plus hallways. Extra space is the adjacency list, the seen set, and the recursion stack, all linear in the size of the graph in the worst case.

The isolated room d is why the outer loop walks rooms and not just the keys that appeared in hallways. If you built the dictionary only from edges, you would drop isolated rooms and under-count. The second assert is a single room with no edges: one component. An empty building should return 0. Add that assert when you copy the function.

Mark a room seen when you start visiting it, not when you finish. If you wait until the end, a cycle can re-enter the room while the first visit is still on the stack. For an undirected edge, the neighbor list includes the parent you just came from. The seen set is what stops you from walking straight back and forth along the same hallway forever.

Shortest paths with BFS

When every edge has the same cost, breadth-first search finds a shortest path. The queue is the fair policy from the stacks and queues page: rooms discovered earlier are explored earlier, so the first time you reach the goal you did it with the fewest hallways.

Original task: return the number of hallways in a shortest route from start to goal. If goal cannot be reached, return None. The graph is undirected.

from collections import deque


def shortest_halls(
    rooms: list[str], halls: list[tuple[str, str]], start: str, goal: str
) -> int | None:
    neighbors: dict[str, list[str]] = {room: [] for room in rooms}
    for left, right in halls:
        neighbors[left].append(right)
        neighbors[right].append(left)

    queue = deque([(start, 0)])
    seen = {start}
    while queue:
        room, dist = queue.popleft()
        if room == goal:
            return dist
        for nxt in neighbors[room]:
            if nxt not in seen:
                seen.add(nxt)
                queue.append((nxt, dist + 1))
    return None


halls = [("a", "b"), ("b", "c"), ("a", "c")]
assert shortest_halls(["a", "b", "c"], halls, "a", "c") == 1
assert shortest_halls(["a", "b"], [("a", "b")], "a", "z") is None

The direct hallway from a to c is one hop. The path through b is two. BFS returns 1 because c is discovered from a before the longer route is explored. If you used DFS, you might stumble down a -> b -> c first and report 2, which is a route but not a shortest route. That is the reason to choose BFS here. DFS was the right tool for components because every node in the component counts, and the order does not.

Time and extra space are linear in rooms plus hallways, same family as the component count. The seen set is what keeps that bound. Without it, a cycle makes the queue grow without limit. Mark a neighbor seen when you enqueue it, not when you dequeue it. If you wait, you can enqueue the same room twice from two parents before either copy is processed, and the algorithm is still correct but no longer linear. On big graphs that difference matters. On small graphs it is still a cleaner invariant: the queue contains each room at most once.

Weighted edges are a different promise

If hallways have different lengths, "number of hallways" is no longer "shortest route," and BFS as written above is the wrong tool. A priority queue that always extends the currently shortest known route is Dijkstra's algorithm, and the priority queue is a heap. The heaps page teaches the heap operation, not the full algorithm. You do not need to recite Dijkstra unless the prompt has unequal weights. You do need to notice the unequal weights and refuse to pretend BFS handles them.

Negative weights break the simple Dijkstra story as well. If the prompt includes them, say that you would need a different algorithm and stop guessing. Inventing a search because the name sounded familiar is worse than a precise "I would not use BFS here."

Practice drill

Draw four rooms and three hallways before you code. Include one isolated room. Implement count_components and point at the line that counts the isolated room. Then add one hallway that creates a cycle and confirm the function still returns. If it hangs, the seen set is wrong. Then implement shortest_halls and add an assert where a longer path exists beside a shorter one, so a DFS accident would fail the test.

Finally, change the graph to directed hallways and remove the line that inserts the reverse edge. Rewrite one assert. The rest of the search stays. That edit is how you learn that the representation was the part that encoded "undirected," not the queue. The common mistakes page summarizes the two failures this drill is meant to prevent: a missing visited set, and a DFS answer reported as a distance.