DFS

O(V + E)

Depth-first search dives down one path as far as it can go, then backtracks and tries the next. It uses a stack — here the recursion (call) stack — so the most recently discovered node is explored first (LIFO). DFS underlies cycle detection, topological sorting, maze solving, and finding connected components.

Click empty space = vertex · click two vertices = edge · drag = moveStart: A
Input graph
Stack
Press ▶ to run
Edit the input and press Play

How it works

  1. Push the start node onto the stack and visit it.
  2. From the current node, go to its first unvisited neighbour and visit it — pushing it on the stack.
  3. When a node has no unvisited neighbours, pop it and backtrack to the previous one.
  4. Repeat until the stack is empty — every reachable node has been visited.

Pseudocode

1DFS(graph, start):2  explore(start)34explore(node):5  visit(node); mark visited       # push a call frame6  for each neighbour of node:7    if neighbour not visited:8      explore(neighbour)           # recurse — go deep first9  # returning = pop the frame (backtrack)