Graph traversal: breadth-first and depth-first

You have a graph — a set of vertices joined by edges — and you want to visit every vertex, exactly once, starting from some vertex and following the edges. This is called a traversal, and it is the beating heart of almost everything we ask a graph to do: find a route on a map, discover everyone connected to you on a social network, flood-fill a region in a painting program, or check whether two web pages are reachable from one another. Before you can solve any of those, you need a systematic way to walk the graph so that no vertex is missed and none is visited twice.

Unlike a list — where "visit everything" just means march from front to back — a graph has no natural order. From any vertex you may have several edges to choose between, and those lead to vertices with more choices still. So the real question is: when you arrive somewhere new and see several unexplored neighbours, which do you follow first? There are two great answers, and they give the two fundamental traversals of all computer science:

Same graph, same starting point, same goal of visiting everything — but two utterly different orders, and two different jobs each is best at. Let's meet them both on one small graph.

Our example graph

Here is the graph we'll use throughout. Seven vertices, A to G, joined by undirected edges. Notice the edge between E and F: it closes a loop A \!-\! B \!-\! E \!-\! F \!-\! C \!-\! A. That loop is a cycle, and it is exactly the sort of thing that will bite us later if we're careless.

A computer stores this as an adjacency list — for each vertex, the list of vertices it is directly joined to. We list neighbours in alphabetical order so every traversal below is perfectly predictable:

A → [B, C] B → [A, D, E] C → [A, F, G] D → [B] E → [B, F] F → [C, E] G → [C]

Keep this picture in your head. Both traversals will start at A and, at each vertex, consider its neighbours in the order shown — the only difference between BFS and DFS is the order they choose to go next.

Breadth-first search: spread out level by level

BFS explores the graph the way ripples spread from a stone dropped in a pond. From the start it visits all the vertices one edge away (level 1), then all the vertices two edges away (level 2), and so on. It never rushes ahead into the distance until it has completely swept the ground closer to home.

The trick that makes this happen is a queue — a first-in-first-out line. Whenever we discover a new vertex we enqueue it at the back of the line; we always process the vertex at the front of the line next. Because near vertices are discovered (and so enqueued) before far ones, they also come out first — and that is precisely what produces the level-by-level order. Step through it:

Here it is in TypeScript, running on our adjacency list. We keep a visited set so we never enqueue the same vertex twice, and a queue array (using shift() to take from the front). Press Run and read the visit order in the Output:

const graph: Record<string, string[]> = { A: ["B", "C"], B: ["A", "D", "E"], C: ["A", "F", "G"], D: ["B"], E: ["B", "F"], F: ["C", "E"], G: ["C"], }; function bfs(start: string): string[] { const visited = new Set<string>([start]); // mark the start at once const queue: string[] = [start]; // the FIFO line of "to visit" const order: string[] = []; while (queue.length > 0) { const v = queue.shift()!; // take from the FRONT of the queue order.push(v); // ...and that's the next visit for (const n of graph[v]) { if (!visited.has(n)) { visited.add(n); // mark BEFORE enqueueing queue.push(n); // add new vertices to the REAR } } } return order; } console.log("BFS visit order:", bfs("A").join(" → "));

Out comes A → B → C → D → E → F → G. See how B and C (level 1) are both visited before any of D, E, F, G (level 2). That is the BFS signature.

Because BFS reaches vertices strictly in order of distance, the first time it discovers a vertex is along a path with the fewest edges possible. In an unweighted graph that is the shortest path — so BFS is the standard way to answer "how few steps from here to there?" (think degrees of separation, or the fewest moves in a puzzle). Just record each vertex's level as you enqueue it. Run this to see the distance of every vertex from A:

const graph: Record<string, string[]> = { A: ["B", "C"], B: ["A", "D", "E"], C: ["A", "F", "G"], D: ["B"], E: ["B", "F"], F: ["C", "E"], G: ["C"], }; function distancesFrom(start: string): Map<string, number> { const dist = new Map<string, number>([[start, 0]]); const queue: string[] = [start]; while (queue.length > 0) { const v = queue.shift()!; for (const n of graph[v]) { if (!dist.has(n)) { dist.set(n, dist.get(v)! + 1); // one edge further than v queue.push(n); } } } return dist; } for (const [vertex, d] of distancesFrom("A")) { console.log(vertex + " is " + d + " step(s) from A"); }

Weighted graphs, where edges have different costs, need a cleverer method (Dijkstra's algorithm) — but for "fewest edges", plain BFS is unbeatable.

Depth-first search: plunge deep, then backtrack

DFS has the opposite temperament. Instead of spreading out, it commits: from the current vertex it picks an unvisited neighbour and dives straight in, then dives again from there, and again — going as deep as the graph allows. Only when it reaches a vertex with no unvisited neighbours (a dead end) does it backtrack to the most recent vertex that still has an unexplored branch, and set off again. It is exactly how you'd explore a maze while trailing a thread behind you: follow a corridor to its end, then reel back to the last junction and try the next corridor.

The structure behind this is a stack — last-in, first-out. The vertex you most recently arrived at is the one you continue from; when it's exhausted you pop back to the one before. The neatest way to write DFS is with recursion, because a recursive call automatically uses the program's own call stack as the DFS stack — diving deeper is a call, and backtracking is a return. Step through the same graph and watch it drill down instead of fanning out:

In code, the recursive version is strikingly short. The visited set does double duty here: it stops us re-visiting, and it is what tells a call it has hit a dead end:

const graph: Record<string, string[]> = { A: ["B", "C"], B: ["A", "D", "E"], C: ["A", "F", "G"], D: ["B"], E: ["B", "F"], F: ["C", "E"], G: ["C"], }; function dfs(start: string): string[] { const visited = new Set<string>(); const order: string[] = []; function visit(v: string): void { visited.add(v); // mark as we arrive order.push(v); // ...and record the visit for (const n of graph[v]) { if (!visited.has(n)) { visit(n); // dive deeper (uses the call stack) } } // loop ends => backtrack (return) } visit(start); return order; } console.log("DFS visit order:", dfs("A").join(" → "));

Out comes A → B → D → E → F → C → G. Follow the thread: from A we dive to B, then D (a dead end — backtrack to B), then E, then F, then C, and finally G. Deep first, wide never.

Recursion hides the stack inside the language. You can make it visible by managing your own stack array — push to go deeper, pop to take the next vertex — which is handy in languages where deep recursion overflows the call stack. To reproduce the recursive order we push each vertex's neighbours in reverse, so the alphabetically-first one ends up on top and is popped next. Any valid depth-first order is "correct", but this makes the two versions agree:

const graph: Record<string, string[]> = { A: ["B", "C"], B: ["A", "D", "E"], C: ["A", "F", "G"], D: ["B"], E: ["B", "F"], F: ["C", "E"], G: ["C"], }; function dfsStack(start: string): string[] { const visited = new Set<string>(); const order: string[] = []; const stack: string[] = [start]; // our own LIFO stack while (stack.length > 0) { const v = stack.pop()!; // take the most recent (LIFO) if (visited.has(v)) continue; // may have been queued twice visited.add(v); order.push(v); // push neighbours reversed, so the first is popped first for (let i = graph[v].length - 1; i >= 0; i--) { if (!visited.has(graph[v][i])) stack.push(graph[v][i]); } } return order; } console.log("DFS (stack):", dfsStack("A").join(" → "));

Same order as the recursive version — because recursion is a stack, just one the language keeps for you.

The one rule you cannot skip: mark vertices visited

Both traversals carried a visited set, and it is not optional decoration — it is what makes them terminate at all. A graph, unlike a tree, can contain cycles: our example loops A \!-\! B \!-\! E \!-\! F \!-\! C \!-\! A. If a traversal doesn't remember where it has already been, it will walk that loop round and round forever.

This runnable proves the point safely. It performs a BFS but counts how many vertices it visits — with the visited guard the count is exactly 7 (each vertex once), and the program finishes. Toggle the USE_VISITED flag to false in your head and you'd have an endless loop; the guard is the only thing standing between you and forever:

const graph: Record<string, string[]> = { A: ["B", "C"], B: ["A", "D", "E"], C: ["A", "F", "G"], D: ["B"], E: ["B", "F"], F: ["C", "E"], G: ["C"], }; function bfsCount(start: string): number { const visited = new Set<string>([start]); const queue: string[] = [start]; let visits = 0; while (queue.length > 0) { const v = queue.shift()!; visits++; for (const n of graph[v]) { if (!visited.has(n)) { // the guard: only NEW vertices go in visited.add(n); queue.push(n); } } } return visits; } console.log("Vertices visited:", bfsCount("A")); // exactly 7 — it terminates

You MUST mark vertices as visited. This is the single most common graph-traversal bug. Because a graph can have cycles, a traversal with no visited set will follow a loop endlessly — enqueueing A, reaching B, coming back to A, going to B again — and never stop. It doesn't just give a wrong answer; it hangs the program (BFS grows its queue without bound; DFS overflows the stack). Here is the fatal version — do not write this:

function bfsBROKEN(start: string): void { const queue: string[] = [start]; while (queue.length > 0) { const v = queue.shift()!; console.log(v); for (const n of graph[v]) queue.push(n); // NO visited check! } // A→B→A→B→... forever }

And don't mix up the two structures. BFS uses a queue (FIFO) and DFS uses a stack (LIFO). Reach for the wrong one and your "BFS" will actually do a depth-first walk, or your "DFS" a breadth-first one — the code runs, produces a plausible-looking list, and is quietly wrong. A memory hook: Breadth is patient and waits its turn in a queue; Depth stacks up commitments and unwinds the last one first.

So which should I use?

Both visit every reachable vertex in the same total time (proportional to the number of vertices plus edges), so the choice is about the order you need, not raw speed:

Learn both cold. They are the two lenses through which nearly every graph algorithm is built — and the difference between them is nothing more than a queue versus a stack.