Home/Graphs/DFS
Search algorithmsCTRL K

DFS

· deep first, backtrack on dead ends
/graphs/dfs
VISITED
1/ 10
entered so far
DEPTH
0
recursion depth now
EDGES
0
looked at so far
BACKTRACKS
0
returns from a node
ORDER
A
visit order
currenton the stacktree edgefinished
10 nodes · 11 edges · seed 7 · 52 steps
step 0 / 51
Nodes10
dfs.ts
1
function dfs(graph: Graph, node: Node, seen = new Set<Node>()) {
2
  seen.add(node);
3
  visit(node);
4
  for (const neighbor of graph.neighbors(node)) {
5
    if (seen.has(neighbor)) continue;
6
    dfs(graph, neighbor, seen);
7
  }
8
  return seen;
9
}
CURRENT STEP
line 3

Visit A at depth 0.

// how it works

Understanding DFS

DFS · the recursion that maps a graph
01

The idea

Depth-first search goes as deep as it can before it goes wide: from the current node it picks the first unvisited neighbour, recurses into it, and only when a node has no unvisited neighbours does it return to whoever called it. The call stack is the path from the source to the current node.

The order nodes are entered and left carries structure: entry and exit times classify every edge as tree, back, forward or cross, which is what cycle detection, topological sorting and Tarjan's strongly connected components are built on.

02

The four stages

1
visitmark u, record its entry
2
descendfirst unvisited neighbour
3
skipalready visited: not a tree edge
4
backtrackno neighbours left: return
03

Complexity

best
O(V + E)every node and edge once
average
O(V + E)linear in the size of the graph
worst
O(V + E)dense graph: E ≈ V²
space
O(V)the recursion stack, up to the longest path
04

Versus its siblings

EDGES EXAMINED · 1 000 NODES, 3 000 EDGES
bfs
6,000
dfs
6,000
dijkstra
6,000
bellman-ford
3M
floyd-warshall
1B
undirected: each edge is seen from both ends
05

Pseudocode

DFS(graph, node)
  mark node visited; visit(node)
  for each neighbour of node
    if neighbour not visited: DFS(graph, neighbour)
06

When to use

Structure questions: is there a cycle, which nodes are reachable, what are the components, what order respects the dependencies.
Mazes and puzzles where memory matters more than path length: the stack holds one path, not a frontier.
07

Pitfalls

Recursion depth equals the longest path: a million-node chain overflows the stack. Use an explicit stack.
The path DFS finds is rarely the shortest; for distances use BFS.
On directed graphs, forgetting to restart from every unvisited node misses whole components.
08

History

Trémaux's 19th-century rule for walking a maze is depth-first search in disguise. John Hopcroft and Robert Tarjan made it the workhorse of graph algorithms in 1973, showing linear-time planarity testing and biconnected components with nothing but DFS and a few timestamps.

Back to Graphs