Graph Traversal (BFS/DFS)

Represent a graph as an adjacency list (or matrix for dense graphs); DFS answers path-existence/connectivity, BFS answers shortest-path-in-an-unweighted-graph. Grids are implicit graphs — treat a 2D matrix as nodes with 4-directional (or 8-directional) neighbors.

Sub-patterns

• A — Connected Components. Count or label groups of connected nodes.
• B — Grid/Matrix BFS-DFS. "Islands"-style problems treating a grid as an implicit graph.
• C — Multi-Source BFS. Start BFS from several nodes at once.
• D — Graph Cloning. Deep-copy a graph while preserving structure.

Practice set (14)

• Easy — Flood Fill, Find if Path Exists in Graph
• Medium — Number of Islands, Clone Graph, Course Schedule (also relevant to Topological Sort), Rotting Oranges, Pacific Atlantic Water Flow, Surrounded Regions, Number of Provinces (also relevant to Union-Find), Walls and Gates (Premium)
• Hard — Word Ladder, Word Ladder II, Bus Routes, Cut Off Trees for Golf Event