BFS and DFS: The Traversal Patterns Everything Builds On

Every promise this course has made comes due today. The last lesson ended with a loaded instruction: to explore a graph, keep a frontier of vertices you've seen but not yet visited, and the container you choose IS the traversal. Time to fire it.

Here is the claim, stated as boldly as it deserves. Breadth-first search and depth-first search, the two most famous graph algorithms in the world, are the same algorithm. Both of them, in full:

function traverse(graph, start):
    frontier = a container holding [start]
    discovered = {start}                    # the visited set
    while frontier is not empty:
        v = take one vertex out of frontier
        visit(v)
        for each neighbor of v:             # the O(degree) question, lesson 16
            if neighbor not in discovered:
                add neighbor to discovered
                put neighbor into frontier

Keep a frontier. Take one out, visit it, add its unseen neighbors. Repeat until empty. The only decision left, the only one, is which vertex comes out when you reach into the frontier. Make the frontier a queue (first in, first out) and the loop explores in rings, nearest first: that's breadth-first search, BFS. Make it a stack (last in, first out) and the loop dives down one path until it dead-ends, then backs up: that's depth-first search, DFS. One loop, two containers. Lesson 6 promised the queue would someday run a search that explores level by level; lesson 13 showed the container swap on trees and promised graphs would sharpen it. This is the lesson both of them were pointing at.

The trap, and the set that disarms it

One line of that pseudocode is load-bearing in a way trees never required: the discovered set.

Take the running graph for today. Same six people as lesson 16, but flip from the follow graph to the friendship graph: mutual, undirected, every edge both ways. Six friendships:

ava  -- ben      ben  -- dev      dev -- ena
ava  -- cleo     cleo -- dev      ena -- finn

Look at the first four edges together: ava to ben, ben to dev, dev to cleo, cleo back to ava. A cycle. Lesson 16 called cycles harmless in a social graph; for a traversal they're a trap. Watch a memoryless walk fall in: start at ava, go to ben. Ben's neighbors include ava, so back to ava. Ava's neighbors include ben. Ben again. Forever. Even a single undirected edge is a two-way street, and a walk with no memory just paces it.

A tree never had this problem: one parent per node, no road back, which is why lesson 13's traversals needed no protection. A graph offers roads back everywhere. So the loop gets a memory: before adding a vertex to the frontier, check the set; already in there, skip it. And since this check runs once per edge, millions of times on a real graph, it has to be fast. "Have I seen this?" answered in O(1) average is exactly the job description of a hash set. Lesson 12's first hero, back for the finale, doing the one thing it has always done.

(One subtlety worth fixing now, because it keeps implementations honest: mark a vertex when it's discovered, i.e. when it enters the frontier, not when it's visited. Otherwise the same vertex can be sitting in the frontier twice. Every walkthrough and every implementation below follows the mark-on-discovery rule.)

Run it with a queue

Frontier is a queue. Start at ava. Every step shows the full state:

Step 3 is the visited set earning its keep: cleo reaches dev a second time, around the other side of the cycle, and the set says "already discovered, skip." No double visit, no infinite loop.

Final visit order: ava, ben, cleo, dev, ena, finn. That order is not random, and it's not just "everything once." Tag each vertex with its distance from ava in hops: ava 0, ben 1, cleo 1, dev 2, ena 3, finn 4. The queue visited them in exactly distance order. A stone dropped at ava, the ripple expanding one ring at a time.

That's the queue's discipline doing the work, not luck. Everything at distance 1 entered the line before anything at distance 2 could even be discovered, because the only way to find a ring-2 vertex is through a ring-1 vertex. First-in-first-out becomes near-before-far, always. Which buys the single most useful guarantee in graph land:

The first time BFS reaches a vertex, it has found a shortest path to it (fewest hops).

The ripple cannot arrive at finn in ring 4 if some 3-hop route existed; the ring-3 wave would have caught him first. BFS doesn't just visit everything. It computes distances, for free, as a side effect of the container.

Breadcrumbs: reconstructing the path

Knowing finn is four hops away is half the prize; usually you want the route. The loop already touches everything it needs, it just has to take notes. One extra move: at the moment of discovery, record who discovered whom. The parent.

From the table: ben and cleo were discovered by ava, dev by ben, ena by dev, finn by ena. Five notes, one per discovery. To get the path to finn, read the trail backwards: finn ← ena ← dev ← ben ← ava, then reverse: ava → ben → dev → ena → finn. Four hops, and the ring argument above proves nothing shorter exists.

This is path reconstruction by parent pointers, and it's not a toy trick. Every route a mapping app draws, every traceroute, ends with something walking a breadcrumb trail backwards from the destination. The breadcrumbs were dropped during the search at no extra charge.

Run it with a stack

Same graph, same start, same loop, same visited set. One change: the frontier is a stack.

Step 2 is the whole personality change in one move. The queue would serve cleo next; she's been waiting longest. The stack doesn't care. It pops dev, the newest discovery, and commits to the path it's on. When finn dead-ends at step 5, popping the older entries is what backtracking is: returning to the last junction with an unexplored branch.

Final order: ava, ben, dev, ena, finn, cleo. Read what happened: the walk went four levels down, to the bottom of the graph, before visiting cleo, who lives one hop from the start. The ripple is gone. This is a spelunker with one rope: follow the passage to its end, and only when it dead-ends, climb back to the last fork and try the other way.

One decision, two worlds

Side by side:

queue (BFS):  ava, ben, cleo, dev, ena, finn     a ripple, ring by ring
stack (DFS):  ava, ben, dev, ena, finn, cleo     a dive, down and back up

Same six vertices, each visited exactly once in both runs, the same neighbors question asked the whole way. In code, the difference is which end of the container you take from: the oldest discovery or the newest. That is the only line that changes.

And here's the loop this closes. Lesson 13's four tree traversals were this exact split all along: preorder, inorder, and postorder are three flavors of DFS (the same dive, differing only in when they pause to look at a node), and level-order is BFS. You have been running both of these algorithms since lesson 13, on graphs so polite (one parent, no cycles) that they never needed a visited set. Trees were the special case. Today the training wheels came off, and the algorithms didn't change.

BFS in production

Reach for the ripple whenever the question contains "nearest" or "shortest."

• Degrees of separation. The "1st / 2nd / 3rd" badges on a professional network are literally the ring number: BFS outward from you through the connection graph. "2nd degree" means "discovered in ring 2," nothing more mystical than that. The old claim that any two people stand six handshakes apart traces to Stanley Milgram's 1960s small-world experiment, which forwarded letters through chains of acquaintances; the ones that arrived took about six hops. Hedged, imperfect, endlessly debated, but that's the phrase's origin: a measured ripple.
• People you may know. Same engine pointed sideways: sweep ring 2, collect friends-of-friends who aren't friends yet, rank by how many ring-1 paths lead to each.
• Web crawlers. Seed URLs go into the frontier, every link is an edge, the crawl expands outward exactly like the six friends did, with the visited set keeping it from chasing its own tail.
• Garbage collection. A tracing collector's mark phase starts from your live variables and traverses everything reachable from them. The textbook description uses three colors of vertex (the tri-color invariant) and is this traversal in spirit. Whatever the wave touches is alive; whatever it never reaches is garbage.

The graph that was never there

Lesson 16 planted implicit graphs; BFS cashes them. A maze: cells are vertices, edges connect cells you can step between, and nobody builds the adjacency list because neighbors are computable: up, down, left, right, minus walls. Run BFS anyway: a queue of cells, a visited set of cells, neighbors conjured on demand. The ripple spreads from the entrance ring by ring, and the first time it touches the exit, that's the shortest escape, guaranteed. The algorithm never notices the graph isn't there. Word ladders ("cat" to "dog", one letter at a time) are the identical move: BFS over words, shortest ladder, no graph in memory. The code section below has the maze version in full.

The honest caveat (and a door)

"Shortest" today means fewest hops: every edge costs 1. The moment edges carry weights (a road map, minutes per segment), fewest hops stops meaning fastest; the three-hop highway beats the two-hop dirt road. The fix is one you already own: swap the container again. Not a queue but a priority queue, lesson 15's heap, always serving the cheapest-total-so-far. That's Dijkstra's algorithm, the first thing waiting in part 2, and notice why it will be cheap to learn: the container-swap insight from this lesson is the entire trick.

DFS's secret identity

Depth-first search is the natural recursive algorithm, because of a fact from lesson 9: every function call pushes a frame, every return pops one. The call stack is a stack you don't see.

function dfs(v):
    visited.add(v)
    visit(v)
    for each neighbor of v:
        if neighbor not in visited:
            dfs(neighbor)

No container in sight, and yet this is DFS, because the container is the call stack. Each recursive call pushes one level deeper down a path; each return pops back to the last junction. The explicit-stack version and the recursive version are the same algorithm in different clothes: one keeps the stack in a variable, one borrows the runtime's.

Run it on the friendship graph from ava (neighbors in listed order) and read the visit order: ava, ben, dev, cleo, ena, finn. The recursion reached cleo through the back of the cycle, from dev: a three-hop path to someone who lives one hop from the start. That nails down the contrast: DFS finds a path; it never promises the shortest one.

One caveat before trusting it everywhere: lesson 9 ended in a stack overflow, and graphs can resurrect it. A graph shaped like a million-vertex chain means a million frames of recursion depth. For huge or unknown graphs, use the explicit stack: same algorithm, ordinary memory, no short leash.

What the dive is for

If DFS can't promise shortest paths, what is it for? Two big answers.

Reachability. Can I get there from here, and what's the full extent of everything I can touch? You've run this with your own mouse: the paint-bucket tool in any image editor. Click a pixel and the fill spreads to every connected same-color pixel, stopping at borders. That's flood fill, and it is a graph traversal: pixels are vertices, touching same-color pixels share an edge, another graph nobody stores. Click, dive, everything reachable changes color. Either traversal works here, because nobody asked for distances, just "everything reachable": order doesn't matter, membership does. The generalization is connected components: traverse from any vertex and you've mapped one island; anything still unvisited, start again from there, second island; count the restarts and you've counted the components. It's how an editor finds distinct regions and how you answer "if this machine dies, which parts of the network can still reach each other."

Structure. Lesson 16 called a dependency cycle a disease (A depends on B, B depends on A, neither builds first) and promised the detection was a traversal question. Here it is: run the dive over the dependency graph tracking each vertex in three states instead of two: never seen, currently on my path (the dive entered it and hasn't returned from it yet), and fully done. Watch it catch one: A depends on B depends on C depends on A. Dive into A (on my path), into B (on my path), into C (on my path). C's dependency is A; check A's state: still on my path. The dive is standing on its own tail. Cycle, caught in the act. The third state is what makes this precise: meeting a done vertex is fine. Two packages depending on one shared library is a diamond, not a loop; the library finished long ago, pass through. Only "on my current path" means trouble. This check, or a cousin of it, is what cargo and npm run across your dependency graph before building. And one more gift hides in the same run: the order vertices turn done, read backwards, is a valid build order, dependencies always first. That trick is called topological sort, it's part 2's first graph move, and you now hold every piece it's made of.

DFS also generates and solves mazes, drives game-tree exploration, and underlies most "visit everything once, cheaply" code you'll meet. The dive is the default when the question is about structure or existence rather than distance.

The bill: O(V + E)

Derive it once; it covers both traversals. Every vertex enters the frontier at most once (the visited set's guarantee). Every vertex that comes out gets its neighbor list scanned once. Summing neighbor-list lengths over all vertices counts every edge once from each end. Total: O(V + E), each vertex once, each edge once. You cannot inspect a whole graph for less.

Notice who made it possible: the adjacency list. Its O(degree) neighbors answer is why the sum collapses to E. An adjacency matrix would charge O(V) per vertex, O(V²) for the whole walk, no matter how sparse the graph. Lesson 16's storage decision became this lesson's speed, which is the course's two questions (how does cost grow, how does it touch memory) agreeing with each other one last time.

Choosing

When either works (plain "visit everything"), DFS is usually the reflex because the recursive version is less code, but on very deep graphs the queue's width problem and the stack's depth problem trade places. Width or depth: know your graph's shape and the choice makes itself.

The real code

Videos stay in pseudocode; here are both traversals on lesson 16's adjacency-list shape, in the three course languages, plus the implicit-graph bonus.

TypeScript carries BFS with parents and path reconstruction, walked closely. DFS follows in both the recursive and iterative forms.

const names = ["ava", "ben", "cleo", "dev", "ena", "finn"]
const friendships: [number, number][] = [
  [0, 1], [0, 2], [1, 3], [2, 3], [3, 4], [4, 5],
]
const adj: number[][] = Array.from({ length: names.length }, () => [])
for (const [a, b] of friendships) {
  adj[a].push(b)
  adj[b].push(a) // undirected: store the edge both ways (lesson 16)
}
 
function bfsParents(start: number): number[] {
  const parent = new Array<number>(adj.length).fill(-1)
  const discovered = new Set<number>([start]) // lesson 12, one last time
  const queue: number[] = [start]
  let head = 0 // moving head: lesson 6 convicted shift() of O(n)
  while (head < queue.length) {
    const v = queue[head++] // take from the FRONT: this line makes it BFS
    for (const next of adj[v]) {
      if (discovered.has(next)) continue
      discovered.add(next) // mark on discovery, not on visit
      parent[next] = v // the breadcrumb
      queue.push(next)
    }
  }
  return parent
}
 
function shortestPath(start: number, goal: number): number[] | null {
  const parent = bfsParents(start)
  if (goal !== start && parent[goal] === -1) return null // never discovered
  const path: number[] = []
  for (let v = goal; v !== -1; v = parent[v]) path.push(v) // walk backwards
  return path.reverse()
}
 
shortestPath(0, 5)!.map((v) => names[v]) // ["ava", "ben", "dev", "ena", "finn"]
 
function dfsRecursive(v: number, visited = new Set<number>(), order: number[] = []): number[] {
  visited.add(v)
  order.push(v)
  for (const next of adj[v]) {
    if (!visited.has(next)) dfsRecursive(next, visited, order) // the call stack is the stack
  }
  return order
}
 
function dfsIterative(start: number): number[] {
  const visited = new Set<number>([start])
  const stack: number[] = [start]
  const order: number[] = []
  while (stack.length > 0) {
    const v = stack.pop()! // take from the BACK: this line makes it DFS
    order.push(v)
    for (const next of adj[v]) {
      if (visited.has(next)) continue
      visited.add(next)
      stack.push(next)
    }
  }
  return order
}
 
dfsRecursive(0) // [ava, ben, dev, cleo, ena, finn]: cleo via the back of the cycle
dfsIterative(0) // [ava, ben, dev, ena, finn, cleo]: the stack-run order

func bfsParents(adj [][]int, start int) []int {
	parent := make([]int, len(adj))
	for i := range parent {
		parent[i] = -1
	}
	discovered := make([]bool, len(adj)) // dense int ids: a bool slice beats a hash set
	discovered[start] = true
	queue := []int{start}
	for len(queue) > 0 {
		v := queue[0]
		queue = queue[1:] // front of the slice: BFS
		for _, next := range adj[v] {
			if !discovered[next] {
				discovered[next] = true
				parent[next] = v
				queue = append(queue, next)
			}
		}
	}
	return parent
}
 
func dfsRecursive(adj [][]int, v int, visited []bool, order *[]int) {
	visited[v] = true
	*order = append(*order, v)
	for _, next := range adj[v] {
		if !visited[next] {
			dfsRecursive(adj, next, visited, order)
		}
	}
}
 
func dfsIterative(adj [][]int, start int) []int {
	visited := make([]bool, len(adj))
	visited[start] = true
	stack := []int{start}
	var order []int
	for len(stack) > 0 {
		v := stack[len(stack)-1]
		stack = stack[:len(stack)-1] // back of the slice: DFS, lesson 6's stack idiom
		order = append(order, v)
		for _, next := range adj[v] {
			if !visited[next] {
				visited[next] = true
				stack = append(stack, next)
			}
		}
	}
	return order
}

std::vector<int> bfs_parents(const std::vector<std::vector<int>>& adj, int start) {
    std::vector<int> parent(adj.size(), -1);
    std::vector<bool> discovered(adj.size(), false);
    std::queue<int> frontier;
    discovered[start] = true;
    frontier.push(start);
    while (!frontier.empty()) {
        int v = frontier.front(); // front: BFS
        frontier.pop();
        for (int next : adj[v]) {
            if (discovered[next]) continue;
            discovered[next] = true;
            parent[next] = v;
            frontier.push(next);
        }
    }
    return parent;
}
 
void dfs_recursive(const std::vector<std::vector<int>>& adj, int v,
                   std::vector<bool>& visited, std::vector<int>& order) {
    visited[v] = true;
    order.push_back(v);
    for (int next : adj[v])
        if (!visited[next]) dfs_recursive(adj, next, visited, order);
}
 
std::vector<int> dfs_iterative(const std::vector<std::vector<int>>& adj, int start) {
    std::vector<bool> visited(adj.size(), false);
    std::vector<int> order;
    std::vector<int> stack = {start}; // a vector IS a stack: push_back/pop_back
    visited[start] = true;
    while (!stack.empty()) {
        int v = stack.back(); // back: DFS
        stack.pop_back();
        order.push_back(v);
        for (int next : adj[v]) {
            if (!visited[next]) {
                visited[next] = true;
                stack.push_back(next);
            }
        }
    }
    return order;
}

Read the TypeScript against the walkthrough. The queue is a plain array with a moving head index instead of shift(), lesson 6's fix for O(n) dequeues. Marking happens at discovery time, inside the neighbor loop, so no vertex can enter the queue twice; parent[next] = v drops the breadcrumb at the same moment. shortestPath is the trail walk: start at the goal, follow parents until the start's sentinel -1, reverse. The output is the exact four-hop route the rings proved minimal.

Put dfsIterative next to bfsParents: the loop is line-for-line the same shape, and pop() versus queue[head++] is the one decision this whole lesson is about. (The two DFS variants visit in slightly different orders because the explicit stack reverses neighbor processing; both are valid depth-first orders.)

In the Go version, the visited "set" is a []bool with dense integer ids: O(1) membership like the hash set, but contiguous, lesson 2 approved. And queue = queue[1:] re-slices rather than copying, fine for a course example; a production queue would use a ring buffer or moving index to avoid pinning the backing array.

In the C++ version, std::queue is an adapter over a deque, the honest FIFO; for the stack, a plain std::vector with push_back/pop_back is idiomatic and cache-friendly. Both functions read as the same loop with the take-from end swapped, which by now is the point.

The bonus walk: maze BFS in TypeScript, the implicit graph made real. No graph object appears anywhere; neighbors are computed at the moment the loop asks:

// maze: "#" wall, "." open. returns fewest steps from start to goal, or -1.
function shortestSteps(
  maze: string[],
  start: [number, number],
  goal: [number, number],
): number {
  const rows = maze.length
  const cols = maze[0].length
  const key = (r: number, c: number) => r * cols + c
  const dist = new Map<number, number>([[key(...start), 0]])
  const queue: [number, number][] = [start]
  let head = 0
  while (head < queue.length) {
    const [r, c] = queue[head++]
    if (r === goal[0] && c === goal[1]) return dist.get(key(r, c))!
    // the implicit adjacency list: up, down, left, right, minus walls
    for (const [dr, dc] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
      const nr = r + dr
      const nc = c + dc
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue // off the map
      if (maze[nr][nc] === "#") continue // wall
      if (dist.has(key(nr, nc))) continue // already discovered
      dist.set(key(nr, nc), dist.get(key(r, c))! + 1) // ring number = parent's + 1
      queue.push([nr, nc])
    }
  }
  return -1 // the ripple died before reaching the goal: no path
}

Same loop as bfsParents with two substitutions: the neighbor list is generated by the four-direction loop instead of read from adj, and the dist map plays both roles, visited set and distance table (a cell is discovered exactly when it gets a distance). The first time the goal comes off the queue, its ring number is the answer, by the same argument that placed finn in ring 4.

The course, from here

That's the course. Look how far the walk went. It started with a six-minute loading screen and one question: what does a step cost. You learned to count (big-O, the growth ladder, the amortized bank account). Then the machine got a vote: one step is a desk reach or a hallway commute, and the memory hierarchy decides which. With both prices in hand you built the structures: arrays, strings, linked lists, stacks and queues. You learned the moves: two pointers, binary search, recursion, divide and conquer, sorting. Then the workhorses: the hash table, trees, the BST, the heap. And finally the shape with no constraints left, the network, and the two traversals every graph algorithm is built on.

What you actually walk away with is a pair of questions. Pick up any structure, any algorithm, any library's documentation, any interviewer's whiteboard problem, and ask: how does the cost grow as n grows, and how does it touch memory? Those two questions are the whole discipline; everything else is detail you now know how to price.

And there is a part 2, because this foundation was built to hold weight. The structures that run production databases and the patterns that close interviews (balanced trees that never tilt, B-trees that organize a disk, caches that forget on purpose, the cheapest-first traversal this lesson teased, dynamic programming) all start from what's now installed. That course is dsa-patterns, and its first graph move is the topological sort you already hold the pieces of. Take the win first: seventeen lessons ago a loading screen took six minutes and you couldn't have said why. Now you could find it, name it, price it, and fix it. See you in part 2.