Depth-First Search

The Idea

Depth-first search takes one neighbour and goes as deep as it can before considering the others. Recursion handles the bookkeeping: the call stack remembers every junction you still owe a visit. The seen set is what keeps a cycle from trapping you.

Real-World Example

A cave diver laying a guideline. At each junction they pick one passage and follow it until it pinches shut, then reel back to that junction and take the next opening. The line on the floor is the stack — it records exactly which turns are still unexplored.

The Code

caves = {"entry": ["hall", "sump"], "hall": ["entry", "gallery"],
         "gallery": ["hall"], "sump": ["entry", "dome"], "dome": ["sump"]}

def dfs(node, seen=None):
    if seen is None:
        seen = []
    seen.append(node)                    # arrive here
    for nb in caves[node]:
        if nb not in seen:
            dfs(nb, seen)                # plunge before siblings
    return seen

print(dfs("entry"))
# ['entry', 'hall', 'gallery', 'sump', 'dome']

g = {"a": ["b", "c"], "b": ["d"], "c": [], "d": []}
out = []

def go(n):
  out.append(n)
  for m in g[n]:
      go(m)

go("a")
print(out)