Graph Traversal: DFS and BFS

What is this?

Traversal is just "visiting every dot in the graph, one at a time, without going in circles." There are two natural styles. DFS (depth-first) is like exploring a maze by always walking forward until you hit a dead end, then backing up — going deep first. BFS (breadth-first) is like ripples spreading from a stone dropped in a pond — you check everything one step away, then everything two steps away. Same map, two ways to walk it, and the choice decides what you can answer.

💡 Fun fact: breadth-first search was invented twice. Konrad Zuse described it in his 1945 PhD thesis (which went unpublished until 1972), and Edward F. Moore reinvented it in 1959 to find the shortest path out of a maze — which is why BFS is sometimes called the "Moore algorithm."

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: almost every "explore this graph" question reduces to one disciplined sweep that carries a visited set plus a frontier. Swap the frontier's data structure and you swap the strategy: a stack/recursion gives DFS (go deep), a queue gives BFS (go wide, shortest hops first). Master that one template and a whole family of graph problems collapses into it.

1. What graph traversal (DFS/BFS) really means

A graph is just nodes plus edges — relationships with no inherent order. Traversal is the act of visiting every reachable node exactly once without getting lost in cycles. Two pieces make that work:

The only structural difference between the two algorithms is what holds the frontier — the nodes discovered but not yet expanded:

That single swap changes everything downstream: DFS naturally follows long paths and backtracks (great for connectivity, cycles, topological order); BFS fans out in concentric rings, so the first time it reaches a node it did so in the fewest edges — the shortest path in an unweighted graph.

⚠️ The number-one beginner bug is omitting the visited set. In any graph with a cycle (and undirected graphs are cyclic by nature — every edge is a 2-cycle), a traversal with no visited set loops forever.

2. Where you'll actually meet this

DFS/BFS are not interview toys — they are everywhere systems reason about relationships:

• Distributed systems. Service-dependency walks, partition/reachability checks ("can this replica reach quorum?"), snapshotting a cluster topology, and deadlock detection (cycle-finding) are all graph traversals over the connectivity graph.
• Networking. Route discovery and link-failure blast-radius are reachability sweeps; BFS underlies shortest-hop routing in unweighted topologies.
• Compute / runtimes. Garbage collectors traverse the object graph (mark-and-sweep is a DFS/BFS with a visited set); build systems topologically order dependency DAGs with DFS.
• Retail-ops / finance. Flow reachability through supply lanes or settlement graphs — "can value/goods move from A to B?" is a same-component query.

If a problem says visit all, connected, path exists, shortest steps, component, cycle, copy the graph — this chapter's template applies.

3. The traversal toolkit (reflexes to build)

1. Always carry a visited set. Mark a node the moment you discover it. This breaks cycles, prevents double work, and guarantees the traversal ends. For object graphs, use a dict/set keyed by the node object.
2. Build an adjacency list, not a matrix. For sparse graphs (the common case) and large n, the list is O(V + E) space; a matrix is O(V²) and dies at scale. Undirected edge [u,v] → add to both lists.
3. DFS = stack / recursion. Plunges deep then backtracks. Natural for connectivity, cycle detection, topological sort, and "clone/mark every node." Watch recursion depth on long chains — go iterative if it can be deep.
4. BFS = queue. Expands in rings; the first arrival at a node is via the fewest edges → shortest path in unweighted graphs, level-order processing, minimum-steps problems.
5. Sweep all components for "do it for the whole graph." A single start only reaches one component. To cover a possibly-disconnected graph, loop over all nodes and launch a fresh traversal from each unvisited one — that's the connected-component sweep (and, with counting, the component count).

4. A 30-second worked example — DFS vs BFS order

Same graph, same start 0, two strategies, two visit orders:

DFS (stack/recursion) dives down one branch fully before the other:

BFS (queue) clears each ring before the next:

Notice BFS reaches 3 and 4 only after everything closer — which is exactly why "first time BFS sees a node" equals "shortest hop count to it." Same visited set, same adjacency list; only the frontier structure differs.

5. Problems in this chapter

▶ Clone Graph

Deep-copy a connected, cyclic, undirected graph (think: snapshot a service-mesh topology into a sandbox). Traverse once carrying an original → copy map that doubles as the visited set, the cycle-breaker, and the shared-structure guarantee. The key move: record a node's copy before recursing into its neighbours.
Pattern: DFS/BFS + clone map. Target: O(N + M) time, O(N) space.

▶ Find if Path Exists in Graph

Decide whether two vertices sit in the same connected component (think: can a packet cross a datacenter fabric?). Flood-fill from the source with a visited set until you touch the destination or the frontier empties.
Pattern: DFS/BFS flood-fill; Union-Find when there are many queries or incremental edges. Target: O(V + E) (BFS/DFS), O(V + E·α(V)) (Union-Find).

6. Common pitfalls 🚫

• No visited set — guaranteed infinite loop on any cycle (and undirected graphs are inherently cyclic). The single most common graph bug.
• Adjacency matrix at scale — O(V²) space is fatal past a few thousand nodes; use a list for sparse graphs.
• Forgetting undirected edges go both ways — add [u,v] to both u's and v's neighbour lists, or half your graph vanishes.
• Recording in the clone map too late — for Clone Graph, insert the copy before recursing, or cycles still loop forever.
• Assuming one start covers the graph — a disconnected graph needs a per-component sweep; one launch only floods one island.
• Reaching for BFS shortest-path on weighted edges — BFS only gives shortest paths when every edge counts the same; weights need Dijkstra/0-1 BFS.

7. Key takeaways

1. One template, two strategies. Visited set + adjacency list + a frontier — stack/recursion makes it DFS, a queue makes it BFS.
2. The visited set is the load-bearing piece. It breaks cycles, kills redundant work, and guarantees termination; never traverse without it.
3. BFS gives shortest unweighted paths for free — first arrival = fewest edges. DFS is the natural fit for connectivity, cycles, and topological order.
4. Reachability = same connected component, and a graph deep-copy = traversal + an original → copy map. Both problems here are this one template wearing different clothes.
5. Why interviewers lean on this family: it's the foundation every harder graph algorithm (Dijkstra, topological sort, Union-Find, SCC) builds on — and it maps directly to real systems work, from GC to partition detection.