Easy Visit & Recurse Graphs
In plain English: Walk every reachable node in a graph by going as deep as possible before backtracking, using recursion.
The call stack acts as an implicit stack — each recursive call goes one level deeper before backtracking.
Prompt
Traverse a graph depth-first using recursion.
Try to write it from scratch before scrolling down.
Solution
def dfs(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node) # mark before recursing to prevent revisits
for nb in graph[node]:
if nb not in visited:
dfs(graph, nb, visited) # call stack acts as implicit stack
return visited