All patterns
DFS / BFS
Visit every node and edge once with a visited set.
time O(V + E)space O(V)
What it is
Depth-first uses recursion or a stack; breadth-first uses a queue and finds shortest paths in unweighted graphs. With a visited set each node and edge is processed once: O(V + E).
When to reach for it
- Connected components, flood fill
- Shortest path in unweighted graph or grid
- Cycle detection, topological order
Clues in the problem
- Grid or adjacency list input
- “Minimum steps” (BFS)
- Explore all reachable states (DFS)
Template
from collections import dequedef bfs(graph, start):seen, q = {start}, deque([start])while q:u = q.popleft()for v in graph[u]:if v not in seen:seen.add(v) # mark when enqueuedq.append(v)return seen
Practice problems
- Number of Islands
- Word Ladder
- Course Schedule
- Clone Graph
Common mistakes
- Marking visited on dequeue, causing duplicate queue entries
- Deep recursion overflow on large graphs
- Forgetting disconnected components