Graph traversal: BFS and DFS
A graph is a set of places and the connections between them. Cities and roads, people and friendships, pages and links, rooms and doors. Each place is a node, each connection an edge, and almost every interesting question about one of them starts with the same move: walk it.
There are two famous ways to walk a graph, and they are taught as two algorithms with two names. They are not. They are one algorithm, and below you can watch the difference arrive: switch between the first two buttons and exactly one line of code changes.
Keep an eye on the container on the right. Everywhere the search knows about and has not been to yet waits in it. Which end it is emptied from is the entire difference between the two names.
1function search(graph, start) {2 const frontier = [start]3 const seen = new Set()4 while (frontier.length > 0) {5 const node = frontier.shift() // from the front6 if (seen.has(node)) continue7 seen.add(node)8 for (const next of graph[node])9 if (!seen.has(next)) frontier.push(next)10 }11}
The graph
numbered in visit order; violet is waiting, dashed is unreached
Taking from the front
0 of 8 visited
The container · a queue
everywhere known about and not yet visited
- Anext out
1 place
Starting at A. It goes into the container on its own, and everything else follows from what comes out.
The one algorithm, the one line that splits it in two, and why the visited set is what makes it finish.
One algorithm
Put the starting place in a container. Then repeat: take one out, mark it as visited, and put each of its neighbours in. Stop when the container is empty. That is the whole thing, and it is the same four lines whichever search you are doing.
The container of places you know about and have not visited is called the frontier, which is a good name: it really is the edge of what has been explored, and it moves outward as the search runs.
The one line
Take from the front of the frontier and the oldest place waiting comes out first. Everything one step from the start is dealt with before anything two steps away, so the search spreads outward in rings. That is breadth-first search, and starting from A it visits A B C D E F G H.
Take from the back and the newest place comes out first, which is always somewhere you have only just heard about. The search commits to whatever it found most recently and runs to the end of that path before it considers anything else. That is depth-first search, and from the same A it visits A C F H G D B E.
A queue gives you one, a stack gives you the other, and nothing else changes. If that seems like too small a difference to deserve two names and two lectures, it is worth sitting with: it is exactly that small, and the consequences are not small at all.
Why the visited set is not bookkeeping
A graph can contain a cycle: a path that leaves a node and comes back to it. A and B are joined, so from A you can reach B, and from B you can reach A, forever.
The visited set is what stops that. Press the third button and watch a search with the check removed: the frontier grows faster than it empties, the same nodes come round again and again, and after 22 turns it has made no progress across a graph of only 8 nodes. It is cut off there because otherwise it would run until the tab died.
This is why a graph is harder than a call tree. A tree has no cycles, so a walk over it cannot revisit anything and needs no memory of where it has been. Add one edge that closes a loop and that stops being true.
What each one is actually for
The orders look like a curiosity until you notice what breadth-first guarantees. Because it finishes every place one edge away before starting on anything two edges away, the first time it arrives somewhere, it has arrived by the fewest edges possible. Ask it for the way from A to H and the answer is a shortest route, for free, with no extra work.
Depth-first promises nothing of the sort. It may reach a place down a long path and never learn that a short one existed. In exchange it gives you something breadth-first cannot: the order in which it starts and finishes with each node tells you about the structure of the graph. Cycle detection, topological ordering, and finding the pieces a graph breaks into are all read off that order.
So the choice is not about taste. Shortest number of steps wants the front of the frontier. Structure, and anything about paths as whole objects, wants the back.
What it costs, and where the cost hides
Each node is taken out once and each edge is looked along once from each of its ends, so both searches cost O(V + E). That is as good as it can be: you cannot answer questions about a graph without at least looking at it.
The memory is the interesting part, and it is where the two differ sharply. Breadth-first has to hold an entire ring of the graph at once, which on a wide graph can be nearly all of it. Depth-first holds one path, which is usually far smaller. On a graph too large for memory, that difference decides which one you can run at all.
Depth-first written recursively trades the explicit container for the call stack, which has a fixed ceiling, so a long path in a large graph is a stack frame for every step of it. The version below keeps its own container on purpose and has no such limit.
Marking on the way in, or on the way out
Watch the frontier closely and you will see the same node sitting in it twice. That is real, not a bug: a node gets added by each neighbour that reaches it before it comes out. The copy that comes out second is thrown away by the check at the top of the loop.
Many textbooks avoid the duplicate by marking a node as visited when it goes in rather than when it comes out. That is a legitimate variation, it keeps the frontier smaller, and for breadth-first it gives exactly the same order. It is not used here for two reasons: the duplicate is the clearest possible argument for why the check exists, and for depth-first, marking on the way in produces an order that is not the one a recursive version would give.
Where the same walk turns up
A maze solver is a graph search where the nodes are junctions. A garbage collector is a graph search where the nodes are objects and an edge is a reference. A build tool works out what to rebuild by walking a graph of files. A spider crawling a site is doing the same, and the choice between covering a site broadly and following one trail deeply is precisely the choice made in one line here.
Dijkstra's algorithm is the next step from breadth-first search and, satisfyingly, it is the same shape again: swap the container for one that always hands back the cheapest place rather than the oldest or the newest. Same algorithm, third container.
Three questions
Pick an answer before you open one. Being wrong here is the useful part, and it is the whole reason to answer rather than read.
Starting from A, one search visits A B C D E F G H and another visits A C F H G D B E. Both run on the same 8 nodes, with the same code. What differs?
With the visited check removed, a search starting at A is still running after 22 turns, even though only 8 nodes exist. Why does it not stop?
In a graph where every edge costs the same, you want the fewest edges from A to H. Which search gives you that as soon as it reaches H?
Problems
Work them before opening the answers. Reading a solution feels like learning and is not.
Read the order backwards
A search on some graph visits:
A B C D E F G H
Every node it visits is at least as far from A as
the one before it. Which search was it?Show the answer →Hide the answer
Breadth-first: it took from the front.Distances that never decrease along the visit order is the defining property, and it is the one worth remembering, because it is what makes breadth-first find fewest-edge routes.
The container decides
You have working breadth-first search.
You need depth-first search instead.
What do you change?Show the answer →Hide the answer
Take from the back of the frontier
rather than the front. One line.If your version uses a queue, swap it for a stack. Everything else, including the visited set and the loop, is untouched.
Remove the check
A search has no visited set. The graph is:
A — B
and it starts at A. Write out the first six
things that come out of the frontier.Show the answer →Hide the answer
A B A B A B …A adds B, B adds A, and nothing ever notices. Two nodes and one edge are enough for a search with no memory to run forever, which is why the check is not an optimisation.
Which one fits in memory
A graph has one starting node joined directly to
one million others, and nothing else.
How many nodes are in the frontier at the widest
point, for each search?Show the answer →Hide the answer
Breadth-first: a million.
Depth-first: a million as well.A trick, and worth the annoyance: both put every neighbour in before taking any of them out, so a single wide node defeats both. The usual claim that depth-first uses less memory is about deep, narrow graphs, and it stops being true the moment one node has a huge number of neighbours.
Find a cycle
Using only a depth-first search, how would you
tell whether a graph contains a cycle?Show the answer →Hide the answer
If the search ever reaches a node that is already
on the path it is currently following, that path
plus the edge just taken is a cycle.The distinction that matters is between a node already visited and a node still on the current path. Reaching a finished node is ordinary; reaching one you are still inside means you have come back round to where you are standing.
What gets asked, and what a good answer sounds like
Say these out loud rather than reading them. The gap between knowing something and being able to say it is the thing interviews measure.
+What is the difference between breadth-first and depth-first search?
Which end of the frontier you take from. Breadth-first takes the oldest place waiting, so it spreads outward in rings; depth-first takes the newest, so it follows one path to the end. Same code otherwise, and both cost O(V + E).
+You need the fewest steps between two places. Which do you use?
Breadth-first, as long as every edge costs the same. It finishes everything one edge away before starting on anything two edges away, so the first time it arrives somewhere it has come by the shortest route. If the edges have different costs, that argument breaks and you want Dijkstra's algorithm, which is the same loop with a container that hands back the cheapest place.
+What happens if you forget the visited set?
On anything containing a cycle, it never terminates. Two nodes joined to each other are enough. It is not an optimisation; it is the termination condition, and it is the difference between walking a graph and walking a call tree.
+Which uses less memory?
Usually depth-first, because it holds one path rather than a whole ring, and on a deep narrow graph that is a large difference. But a single node with a million neighbours puts a million entries in the frontier either way, so the answer is about the shape of the graph rather than about the algorithm.
+Why is depth-first usually written recursively?
Because the call stack is already a stack, so the frontier does not have to be written down at all. It is shorter to read and it is the same algorithm. The cost is that the depth of the graph becomes the depth of the recursion, with a stack frame for every step, and a long enough path will exhaust it.
Know someone stuck on this? Send it to them.
A classmate, a study group, someone learning this on their own at midnight. The link opens the lesson set up exactly as you have it, the same function and the same number, and runs from the first step so they watch the whole thing build rather than landing in the middle of it.
Also in this course
Recursion: how a function calls itself
Depth-first search written recursively has no visible container at all. The stack is still there; it is the one this lesson draws.
Start there →