Lesson 19 — DFS traversal

DFS: go deep, then backtrack

Depth-first search (DFS) follows one path as far as it can before backing up and trying the next branch. The easiest way to write it is recursion: visit a node, then call dfs on each unvisited neighbour. A seen set prevents loops.

def explore(room):
    visited.add(room)
    for door in rooms[room]:
        if door not in visited:
            explore(door)

Why it matters: DFS finds cycles, solves mazes, and works out the order to install software dependencies.