cf.completefrontend
GRAPHS · CORE

Depth-first search (DFS)

Explore a graph by following one path as deep as it goes, then backing up to try the next unexplored branch.

Time O(n + e)Space O(n)10 practice problemsStep-through picture

The idea

Depth-first search, or DFS, explores a graph the way you might explore a maze: keep walking forward through new rooms, and when you hit a dead end, walk back to the last room that still has an unexplored door.

The easiest way to write it is with recursion, which means a function that calls itself. visit(node) marks node as visited, then calls visit on each neighbor that hasn't been visited yet. When all neighbors are done, the function returns, which is the "walking back" part.

DFS does not find shortest paths. It answers questions about what is connected: can I reach this node, how many separate groups are there, how big is each group, and does the graph have a loop. It is also the base for topological sort, cycle detection, and finding bridges.

An everyday example

Exploring a maze with a ball of string

You enter a maze holding a ball of string that unrolls behind you. At each room you pick a door you haven't tried and go through. When a room has no untried doors, you follow the string back one room and try that room's next door. You chalk an X on every room you enter so you never explore it twice.

How the example maps to the code
In the exampleIn the code
Walking through a new doorCalling visit(next)
Chalking an X on a roomvisited[node] = true
Skipping a room that has an Xif (!visited[next])
Following the string backvisit returning to its caller
The order you entered roomsThe order list

From the slow way to depth-first search (dfs)

  1. Say you need every node that start can reach. A slow way is to repeat rounds: in each round, scan all edges and add any node next to something already found. A long chain may need n rounds of e checks each, about n * e work.
  2. Most of that work is repeated. A node's neighbors only need to be looked at once, right after the node is found. After that they can't add anything new. So look at them immediately, and keep a mark on each found node so it is never handled twice.
  3. Which found node should you look at next? For reachability, any order works. Taking the most recent one gives a very short program: a function visit(node) that calls itself for each new neighbor. The call stack remembers where to come back to when a branch is finished.
  4. One detail makes it safe on graphs with loops: set the mark before looking at any neighbor. Then a path that leads back to this node sees the mark and stops. That recursive function is depth-first search.

How it works

  1. Make visited, one false per node, and an empty order list for the visit order.
  2. Define visit(node): set visited[node] = true and push node to order.
  3. Inside visit, loop over each neighbor next of node.
  4. If next is not visited, call visit(next). This goes one level deeper before trying the next neighbor.
  5. When the loop ends, visit returns, and the caller continues with its own next neighbor.
  6. Call visit(start). When it returns, every node reachable from start is visited.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function dfs(graph, start) {
  2. const visited = new Array(graph.length).fill(false);
  3. const order = [];
  4. function visit(node) {
  5. visited[node] = true;
  6. order.push(node);
  7. for (const next of graph[node]) {
  8. if (!visited[next]) visit(next);
  9. }
  10. }
  11. visit(start);
  12. return order;
  13. }

How fast it is

TimeO(n + e)
Extra memoryO(n)

Each node is visited once and each neighbor list is read once. visited, order, and the call stack hold at most n entries.

  • Best caseO(n)

    start has no neighbors. One call runs, but making visited costs n steps.

  • Average caseO(n + e)

    Each node reachable from start gets one call and its list is read once.

  • Worst caseO(n + e)

    Everything is reachable, so every node and every edge is touched.

Common mistakes

  • Marking a node as visited after the recursive calls instead of before. Two neighbors can then lead back into each other forever.
  • Expecting DFS to find the shortest path. It finds a path, often a long one. Use BFS for fewest steps.
  • Running DFS from only one node when the graph has several separate parts. Loop over every node to reach them all.
  • Recursing on a very deep graph and overflowing the call stack. Switch to an explicit stack for long chains.

When to use it

Look for these clues in a problem:

  • The question asks if one node can reach another, or which nodes can be reached at all.
  • You need to count or measure connected groups: islands, friend circles, components.
  • You need every path, not just the shortest one.
  • The answer depends on finishing all of a node's descendants first, as in dependency order or cycle checks.

Check yourself

Answer each one in your head first, then open it.

Why must visited[node] = true come before the neighbor loop?

If it came after, a neighbor that links back would see node as unvisited and call visit(node) again, which can recurse forever on any loop.

How many times is visit called in the trace?

Six times, once for each node reachable from 0. Node 6 is never visited, so there is no seventh call.

Do DFS and BFS from the same start visit the same nodes?

Yes, both visit exactly the nodes reachable from the start. Only the order differs, and only BFS's order follows distance.

How deep can the call stack get?

Up to n calls, when the graph is one long chain and the search starts at one end. In the trace it reached 5 calls.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 10 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

Two facts make DFS correct. The first: every node in order is reachable from start. visit is only ever called on start or on a neighbor of a node that is already being visited, so each visited node is joined to start by a chain of edges.

The second: when visit(x) returns, every neighbor of x is visited. The loop looks at each one and either finds it marked or visits it. Now take any node reachable from start and the path to it. start is visited, so its next node on the path is visited, and so on along the path. So every reachable node ends up in order.

It always ends. A node is marked before its loop starts, and visit is only called on unmarked nodes, so each node gets at most one call. Each call reads one neighbor list once. That gives n calls and e neighbor checks at most (twice that for undirected edges).

Going deeper

3 more ideas

Why every reachable node gets visited

Suppose some node x can be reached from start but never gets visited. Follow the path from start to x: at some point it goes from a visited node a to an unvisited node b. But when visit(a) ran, it looped over all of a's neighbors, including b, and would have called visit(b). That's a contradiction, so every reachable node is visited.

Counting separate groups

To count connected groups (components), loop over every node. When you find one that isn't visited yet, add one to a counter and call visit on it. That call marks the whole group, so the loop only starts a new count for nodes in a new group. The same loop can measure each group's size by counting the visits.

Deep graphs and the call stack

Each recursive call uses some memory on the call stack. A long chain of 100,000 nodes can make the browser throw "Maximum call stack size exceeded". For very deep graphs, use an explicit stack array instead: push the start, and in a loop pop a node, skip it if visited, mark it, and push its unvisited neighbors.

Work it by hand

Every step in a table, with why

Depth-first order from node 0 in an undirected graph with 7 nodes. Node 6 has no edges.

graph = [[3, 1], [5, 0, 4], [3], [0, 5, 2], [1], [3, 1], []], start = 0

StepCall stacknodenextorderWhy
100-[0]visit(0) marks 0 as visited and adds it to order.
20 33-[0, 3]The first neighbor of 0 is 3. It is new, so the search goes into it before looking at 0's other neighbor.
30 330[0, 3]The first neighbor of 3 is 0, which is visited. Skip it.
40 3 55-[0, 3, 5]The next neighbor of 3 is 5. It is new, so go deeper.
50 3 5 11-[0, 3, 5, 1]5 skips 3, then finds 1 new. The stack is now 4 calls deep.
60 3 5 1 44-[0, 3, 5, 1, 4]1 skips 5 and 0, both visited, then goes into 4.
70 3 5 1 441[0, 3, 5, 1, 4]4's only neighbor is 1, already visited. visit(4) returns. This is the deepest point: 5 calls.
80 33-[0, 3, 5, 1, 4]1 and 5 have no neighbors left, so both return. The search backs up to 3, which still has one neighbor to try.
90 3 22-[0, 3, 5, 1, 4, 2]3's last neighbor, 2, is new.
100 3 223[0, 3, 5, 1, 4, 2]2 only touches 3, which is visited. visit(2) returns, then visit(3) returns.
11001[0, 3, 5, 1, 4, 2]Back in visit(0), its second neighbor 1 was visited long ago, deep inside the first branch. Skip it and return.

It returns [0, 3, 5, 1, 4, 2]. Node 1 is a direct neighbor of 0 but comes fourth, because the first branch reached it first. Node 6 is never visited because no edge reaches it.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Depth-first search (DFS)O(n + e)O(n)You need reachability, groups, cycles, or finish order, and recursion depth is safe.
Breadth-first searchO(n + e)O(n)You need the fewest edges to each node. It also has no recursion depth problem.
Union-findO(e · α(n))O(n)Edges arrive one at a time and you keep asking "are these two connected yet?" between arrivals.

Extra memory: O(n): visited and order hold up to n entries, and the call stack can be n calls deep on a long chain like 0-1-2-3-....

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Depth-first search (DFS) and the other approaches, on a scale where each line up is 10 times more steps.
  • Depth-first search (DFS), Breadth-first search O(n + e)
  • Union-find O(e · α(n))
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Depth-first search (DFS)202,0002 million
Breadth-first search202,0002 million
Union-find101,0001 million

Inputs that need care

5 tricky inputs
start has no edges
visit(start) marks it, finds an empty list, and returns. The result is [start].
A graph with a loop, such as 0-1, 1-2, 2-0
When the search comes back around to 0, the mark is already set, so it doesn't go in again. The marks are what stop endless recursion.
Several separate pieces, like node 6 in the trace
One call only covers the start's piece. To cover everything, loop over all nodes and call visit on each one that isn't visited yet.
A chain of 200,000 nodes
The recursion goes 200,000 calls deep and throws "RangeError: Maximum call stack size exceeded". Use an explicit stack array for inputs that deep.
Neighbor lists in a different order
The set of visited nodes is the same, but order changes. If a problem needs one exact order, such as smallest neighbor first, sort each list first.

Variations and follow-ups

Twists interviewers add

Explicit stack

Push start. In a loop, pop a node, skip it if visited, mark it, and push its unvisited neighbors. Push them in reverse if you want the same order as the recursive version. This has no depth limit.

Counting groups

Loop over every node and start a new visit from each unvisited one, adding 1 to a counter each time. The counter is the number of connected groups, and counting calls per start gives each group's size.

Finish order

Push the node after its loop instead of before. That is post-order: each node appears after everything it leads to. Reversed, it is a topological order, which is how DFS topological sort works.

All paths with backtracking

Unmark a node when its call returns. Now the search can pass through a node again by another route, which lists every simple path. That can take exponential time, so it is only for small graphs.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "can reach", "connected", "how many groups", "islands", or "is there a path" with no word about shortest.
  • Explain the mark first: "I mark a node before visiting its neighbors, so loops can't make me go around forever". Then the rest of the code is short.
  • Test by hand on a triangle (a loop) and on a graph with an isolated node. The triangle checks the mark, the isolated node checks the outer loop if you need one.
  • The usual follow-up is "what if the graph is very deep?". Answer: recursion can overflow the call stack, so switch to an explicit stack array, which uses heap memory instead.

Where frontend code uses it

The same idea in real UI code
  • document.querySelectorAll returns elements in document order, which is the order a depth-first walk of the DOM tree visits them.
  • Bundlers walk the import graph depth-first from an entry file to find every module that must be in the bundle; anything never visited can be dropped.
  • React renders and commits a component tree by walking it depth-first, child before sibling.

Related algorithms