Module 8

Graphs: BFS & DFS

A graph is nodes plus edges, no other rules — social networks, dependency graphs, road maps, and (worth noticing) trees and linked lists are just graphs with discipline. The default representation is the adjacency list: a map from node → list of neighbors. O(V + E) space, cheap neighbor iteration. Its alternative, the adjacency matrix, answers “is there an edge u–v?” in O(1) but costs O(V²) space — mention it, then use the list. Many problems arrive as a grid; a grid is a graph where each cell's neighbors are up/down/left/right.

Unlike a tree, a graph can contain cycles, so traversal needs memory of where it's been — the visited set. Mark a node when you first see it, never process it twice. Forgetting this (or marking too late, when you pop rather than when you push) is the classic graph bug: an infinite loop on the first cycle, or exponential revisits.

🎛 BFS vs DFS — swap the container, change the explorer

visited: —

queue: [A]

Same skeleton, one swap: BFS pulls from a queue (explores by distance — first time you reach a node is the shortest unweighted path) while DFS pulls from a stack (dives deep — natural for cycle detection, connectivity, topological sort). The seen set is what stops the A–B–D–A cycle from looping forever — forgetting it is the classic graph bug.

One skeleton, both algorithms

def traverse(graph, start):
    seen = {start}
    work = [start]                  # the only decision:
    while work:
        node = work.pop(0)          #   pop(0)/deque.popleft() = queue = BFS
        # node = work.pop()         #   pop()               = stack = DFS
        process(node)
        for nb in graph[node]:
            if nb not in seen:
                seen.add(nb)        # mark when PUSHED, not when popped
                work.append(nb)
# Either way: O(V + E) time, O(V) space — every node and edge once.

BFS explores in rings of increasing distance, so the first time it reaches a node is a shortest path in edges— that's why “minimum steps/moves/hops” means BFS. DFS commits to a path until it dead-ends — natural for connectivity, counting islands, cycle detection, and anything backtracking-shaped. DFS is also recursion-friendly (the call stack isthe stack).

The follow-ups worth one sentence each

Weighted shortest path — BFS no longer suffices; Dijkstra's algorithm is BFS with a priority queue (no negative weights).
Topological sort — ordering a DAG so every edge points forward (build systems, course prerequisites): repeatedly take a node with no remaining incoming edges (Kahn's), or DFS and reverse the post-order.
Connected components — loop over all nodes, launch a traversal from each unvisited one, count the launches.
Cycle detection — undirected: a visited neighbor that isn't your parent; directed: a node revisited while still on the current DFS path.

Say it out loud

“The problem says minimum number of moves — unweighted shortest path, so BFS.”
“I'll mark visited at enqueue time so nothing enters the queue twice.”
“Traversal is O(V + E) — each node and each edge handled once.”

← Trees Next: OOP & design patterns →