Graphs & Grids (BFS/DFS/Topo)
Use for components, shortest path in unweighted, island counting, topological sort (DAG).
What this pattern is
Model relationships with adjacency lists or grids. Use BFS for shortest path in unweighted graphs, DFS/BFS for components, and topological sort for DAG ordering and cycle detection.
Exercise: bfs
Task: Given n nodes (0..n-1) and undirected edges, compute shortest-path distances from src in an unweighted graph.
Example: n=6, edges=[[0,1],[0,2],[1,3],[2,3],[3,4],[4,5]], src=0 → dist=[0,1,1,2,3,4]
Edge cases: disconnected nodes (distance Infinity), self-loops.
Your Solution
Exercise: numIslands
Task: Given an m×n grid of '1' (land) and '0' (water), return the number of islands (4-directionally connected land).
Example:
["1","1","0","0","0"]
["1","1","0","0","0"]
["0","0","1","0","0"]
["0","0","0","1","1"]
→ 3
Edge cases: all water, all land, skinny grids.
Your Solution
Exercise: topoOrder
Task: Given a directed graph with n nodes and edges u→v, return a topological ordering or [] if a cycle exists.
Example: For course prerequisites edges, return a valid course order or empty if impossible.
Edge cases: multiple valid orders, isolated nodes, cycles.