Easy Stack + Visited Graphs
In plain English: Walk every reachable node in a graph by going as deep as possible before backtracking, using a stack.
Replacing the BFS queue with a stack switches from breadth-first to depth-first — LIFO explores deep before wide.
Prompt
Traverse a graph depth-first using an explicit stack.
Try to write it from scratch before scrolling down.
Solution
def dfs_iterative(graph, start):
visited = {start}
stack = [start] # stack = LIFO = depth first
order = []
while stack:
node = stack.pop()
order.append(node)
for nb in graph[node]:
if nb not in visited:
visited.add(nb)
stack.append(nb)
return order