Graphs & Traversal: BFS and DFS

A tree is a graph that's been put on a leash: one root, no cycles, everything flowing downward. Drop those restrictions and you get a graph: nodes connected by edges in any pattern at all. Your friends list, a road map, the web's links, a dependency chart, they're all graphs. And almost every interesting question about them ("can I get from here to there? what's the shortest route?") comes down to one skill: visiting the nodes in a sensible order.

Nodes, edges, and how to store them

A graph is two things: a set of nodes (also called vertices) and a set of edges connecting pairs of them. That's the entire definition. The sample graph in this lesson has six nodes (A, B, C, D, E, F) and these edges: A–B, A–C, B–D, B–E, C–F, E–F.

The standard way to store that in code is an adjacency list: a map from each node to the list of nodes it's directly connected to. It's compact (you only record edges that exist) and it instantly answers the question traversals ask constantly, "who are this node's neighbours?"

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

This is an undirected graph, so each edge shows up on both ends: A lists B as a neighbour, and B lists A right back. To visit every node reachable from a starting point, you have two classic strategies, and they differ only in which neighbour you explore next.

BFS: explore in rings, nearest first

Breadth-first search fans out level by level. Start at A, visit all of A's direct neighbours, then all of their unvisited neighbours, and so on, exploring the graph in expanding rings of distance. The engine that makes this work is a queue: first in, first out. You enqueue a node's neighbours, then process them in the order they arrived, which is exactly the order of increasing distance from the start.

Step through it from A and watch the wavefront spread outward one ring at a time.

Because BFS reaches every node by the fewest possible hops, it's the go-to for shortest path in an unweighted graph. The first time it touches a node, it got there by the shortest route. There's no shorter one, or an earlier ring would have found it. "Fewest connections between two people," "minimum moves to solve the puzzle," "nearest matching tile," all BFS.

DFS: commit to a path, then backtrack

Depth-first search does the opposite. From A it picks one neighbour and dives, then from that node picks one neighbour and dives again, chasing a single path as deep as it goes before it ever looks at a sibling. When it hits a dead end (a node whose neighbours are all visited), it backtracks to the last node with an unexplored branch and tries that.

The natural engine for DFS is a stack (last in, first out) and recursion gives you one for free, since the call stack is a stack. Each recursive call goes one level deeper. Each return backtracks one level up.

Notice how different the visit order feels: instead of spreading evenly, it plunges down one branch, exhausts it, then climbs back. DFS is the right tool when you need to fully explore: detecting cycles, finding connected components, generating permutations, topological sorting a dependency graph. It doesn't promise shortest paths, but it's lighter on memory and maps perfectly onto recursive problems.

Both, in code

Here's the same sample graph traversed both ways: BFS with a deque as the queue, DFS with plain recursion. Both track a visited set so a cycle never sends you in circles. Run it and compare the two orders.

The structural difference is one line. BFS pulls from the front of a queue (popleft), so nodes come out in arrival order, nearest first. DFS recurses on a neighbour immediately, riding the call stack down before touching the next sibling. The seen set is non-negotiable in both: without it, any cycle (and an undirected graph is full of them) loops forever.

Where to go next

A graph is nodes plus edges, an adjacency list stores it compactly, and two traversals cover most of what you'll ask of one: BFS with a queue for nearest-first and shortest unweighted paths, DFS with recursion for going deep and exhaustive exploration. Pick by the question: distance wants breadth, exploration wants depth.

Next we change gears to a different kind of efficiency: not visiting things faster, but refusing to recompute the same answer twice. Next: Intro to Dynamic Programming: Memoization. The deque and recursion here build on hash maps and sets (that seen set) and recursion, worth a revisit if either felt shaky.