Graph Traversal: BFS and DFS — cheat sheet — Algorithms & Data Structures with Python

BFS and DFS visit every reachable node; they differ only in visit order, and that order decides what each one solves.

Core vocabulary

Graph: nodes (vertices) joined by edges; V = node count, E = edge count.
Adjacency list: dict mapping each node to its neighbor list; storage is O(V + E).
Traversal: visit reachable nodes by following edges. Edges can be undirected or directed.
Visited set: remembers seen nodes; membership check is O(1). Every correct traversal keeps one, or it loops forever on a cycle.

Explores in layers, spreading outward like a ripple: start, then 1 edge away, then 2.
Uses a queue (FIFO). Python collections.deque: append (back) and popleft (front), both O(1).
Pop front, scan neighbors, enqueue unseen ones to the back. Mark visited on enqueue.
Headline feature: first time a node is seen is via the fewest edges, so BFS gives the shortest path in an unweighted graph. Recover it with a parent dict.

A          layer 0
B  C       layer 1
D  E  F    layer 2

Go as deep as possible down one path, then backtrack to the last unvisited neighbor.
Uses a stack (LIFO). Natural form is recursion; Python’s call stack is the stack.
Recursive: mark on visit, recurse into each unvisited neighbor.
Iterative version uses an explicit list-as-stack: pop from top, mark on pop, guard with if node in visited: continue. Order may differ from the recursive one.
Suited to: full exploration, connected components, all-paths, cycle detection, topological sort, flood fill.

Time O(V + E): each node processed once (V), each edge looked at a fixed number of times (E). Visited set prevents repeats.
Space O(V): visited set plus queue / stack / recursion depth, each bounded by V. (Graph storage O(V + E) is input, not extra space.)

Use BFS when…	Use DFS when…
Shortest path in unweighted graph or grid	Just need to visit every node, order irrelevant
Nodes in order of distance (nearest first)	Exploring all paths, cycles, components
Answer likely close to the start	Deep/wide graph, want low memory on wide layers

Summary: BFS for shortest / nearest, DFS for full exploration and structure.

A grid is a graph in disguise: each cell is a node; neighbors are up/down/left/right computed from coordinates. BFS finds the shortest maze path.
Forgetting the visited set: infinite loop on any cycle (most common bug).
BFS: mark on enqueue, not dequeue, or nodes get enqueued many times.
Never use list.pop(0) as a BFS queue: it is O(n). Use deque.popleft.
Avoid mutable default args (visited=set()): shared across calls; guard with if visited is None.
Recursive DFS caps at ~1000 nested calls (RecursionError); use the iterative stack for deep graphs.
Grids: check bounds before indexing and skip walls.