Graph AlgosGraph Algorithms

Depth-First Search (iterative)

Explore a graph by following one path as deep as possible before backtracking, using recursion or an explicit stack.

Graph — One edge per line: "A B". Optional "source: A" / "target: F" lines.

Stack (top → bottom)

Discovery order

empty

1/18Start DFS from A. The explicit stack replaces the recursion: the node on top is explored next, so we dive deep before going wide.

Current nodeOn the stackVisited (label = discovery order)DFS tree edge

PseudocodeLearn Depth-First Search (DFS) →

1stack = [source]; visited = {}; order = []
2while stack not empty:
3  u = stack.pop()
4  if u in visited: continue
5  visited.add(u); order.append(u)
6  for v in reversed(neighbors(u)):
7    if v not in visited: stack.push(v)

Complexity

best O(V + E)

avg O(V + E)

worst O(V + E)

space O(V)

Speed