ZERO / HERO
One corridor to the end

Depth-First Search

The analogy

In a maze you pick a corridor and follow it as far as it goes. Dead end? Back up to the last junction and take the next corridor. DFS commits to a path completely before considering alternatives.

Visualizer

One corridor to the end

step 1 / 15
ABCDEFGH

Start at A. A stack holds where to go next — last in, first out.Stack: A

def dfs(adj, start):
    seen, stack, order = set(), [start], []
    while stack:
        v = stack.pop()          # LIFO
        if v in seen:
            continue
        seen.add(v)
        order.append(v)
        stack.extend(adj[v])
    return order
Check yourself

Which finds the shortest unweighted path?