Depth-First Search

Explore as far along one branch as possible before backtracking, using a stack. Visits the same nodes as BFS but in a completely different order.

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

stack = [start]
visited = {}
while stack:
  u = stack.pop()
  if u in visited: continue
  visited.add(u)
  for v in neighbours(u):
    if v not in visited: stack.append(v)