Dive one branch all the way down before backtracking. Stack-shaped traversal — natural fit for recursion.
Pick a start node, then BFS or DFS, then Step.
What you just watched
DFS uses a stack (or, naturally, the call stack via recursion). Visit a node, mark it seen, then recurse into one unseen neighbour. Only when that branch is fully explored do you return and try the next neighbour.
That depth-first order is what makes DFS great for connectivity (mark a whole connected component), cycle detection (notice a back-edge while descending), and topological sort (post-order on a DAG).
DFS does not find the shortest path in general — the first time it reaches a node may be along a long winding route. Use BFS for shortest path in unweighted graphs.
def dfs(graph, start, seen=None):
if seen is None: seen = set()
if start in seen: return
seen.add(start)
process(start)
for n in graph[start]:
dfs(graph, n, seen)