Graphs
BFS, DFS, shortest paths, topological sort and union-find.
11 notes · 59 min total
Questions0 of 61 done
Warm up with these before Phase 1.
Patterns
- 1Representation, BFS/DFS & ComponentsHow to store a graph, when to reach for BFS or DFS, and how to count connected components without redoing work.7 min
- 2Grid Flood FillTreat a grid as a graph, flood each island once, and see why nested loops plus DFS still cost only O(MN).5 min
- 3BFS Shortest Path & Multi-Source BFSUse BFS layers to get the fewest steps in an unweighted graph, and seed every source at once to solve nearest-source problems in O(mn).5 min
- 4Cycle DetectionFind cycles with a parent check (undirected) or an on-path set (directed), and cache finished nodes to stay O(V + E).5 min
- 5Topological SortOrder tasks that depend on each other with Kahn's in-degree queue or DFS post-order, and use the same pass to detect a cycle.6 min
- 6Dijkstra's Algorithm (and A*)Find the cheapest path in a graph with non-negative weights using a min-heap, skip stale entries, and know when A* is worth it.8 min
- 7Bottleneck / Minimax PathsUse Dijkstra when a path's cost is its worst edge, its weakest cell or a product, not a sum, and see why the greedy pop still works.4 min
- 8Modeling Problems as Weighted GraphsTurn ratios, directions, geometry and puzzle states into nodes, edges and weights so a standard traversal can solve them.5 min
- 9Union-Find (DSU)Track groups that keep merging with find and union, count components, catch undirected cycles, and spot DSU hiding in non-graph problems.6 min
- 10Minimum Spanning TreeConnect every node at the lowest total cost with Kruskal (sort edges + Union-Find) or Prim (a heap), and see how Prim differs from Dijkstra.4 min
- 11Bipartite Graphs / 2-ColoringSplit a graph into two teams with BFS 2-coloring, and know that it fails exactly when the graph has an odd cycle.4 min