Depth-First Search

Explore a graph as deeply as possible before backtracking. Uses a stack (or recursion). Natural fit for topological sort, cycle detection, and maze exploration.

time O(V + E)

space O(V)

Input

Press Tab out of the box or click Resetto regenerate frames from the current input.

Visualization

No frames yet — edit input and click Run.

—

Pseudocode

dfs(u):
  visited.add(u)
  for v in neighbours(u):
    if v not in visited:
      dfs(v)