πΈοΈ Part 5: Graph Algorithms
Learn to see graphs in problems and solve them efficiently. BFS, DFS, trees, Union-Find, and Kruskal's MST β the core of USACO Silver.
π 4 Chapters Β· β±οΈ Estimated 2-3 weeks Β· π― Target: Reach USACO Silver level
Part 5: Graph Algorithms
Estimated time: 2β3 weeks
Graphs are everywhere in competitive programming: mazes, networks, family trees, city maps. Part 5 teaches you to see graphs in problems and solve them efficiently.
What Topics Are Covered
| Chapter | Topic | The Big Idea |
|---|---|---|
| Chapter 5.1 | Introduction to Graphs | Representing graphs; adjacency lists; types of graphs |
| Chapter 5.2 | BFS & DFS | Traversal, shortest paths, flood fill, connected components |
| Chapter 5.3 | Trees & Special Graphs | Tree traversals; Union-Find; Kruskal's MST |
| Chapter 5.4 | Shortest Paths | Dijkstra, Bellman-Ford, Floyd-Warshall, SPFA |
What You'll Be Able to Solve After This Part
After completing Part 5, you'll be ready to tackle:
-
USACO Bronze:
- Flood fill (count connected regions in a grid)
- Reachability problems (can cow A reach cow B?)
- Simple BFS shortest paths in grids/graphs
-
USACO Silver:
- BFS/DFS on implicit graphs (states rather than explicit nodes)
- Multi-source BFS (distance to nearest obstacle/fire)
- Union-Find for dynamic connectivity
- Graph connectivity under edge additions
- Tree problems (subtree sums, depths, LCA)
Key Algorithms Introduced
| Technique | Chapter | Time Complexity | USACO Relevance |
|---|---|---|---|
| DFS (recursive & iterative) | 5.2 | O(V + E) | Connectivity, cycle detection |
| BFS | 5.2 | O(V + E) | Shortest path (unweighted) |
| Grid BFS | 5.2 | O(R Γ C) | Maze problems, flood fill |
| Multi-source BFS | 5.2 | O(V + E) | Distance to nearest source |
| Connected components | 5.2 | O(V + E) | Counting disconnected regions |
| Tree traversals (pre/post-order) | 5.3 | O(N) | Subtree aggregation |
| Union-Find (DSU) | 5.3 | O(Ξ±(N)) β O(1) | Dynamic connectivity |
| Kruskal's MST | 5.3 | O(E log E) | Minimum spanning tree |
| Dijkstra's algorithm | 5.4 | O((V + E) log V) | SSSP on non-negative weighted graphs |
| Bellman-Ford | 5.4 | O(V Γ E) | SSSP with negative edges; detect negative cycles |
| Floyd-Warshall | 5.4 | O(VΒ³) | All-pairs shortest paths on small graphs |
| SPFA | 5.4 | O(V Γ E) worst | Practical Bellman-Ford with queue optimization |
Prerequisites
Before starting Part 5, make sure you can:
-
Use
vector<vector<int>>for adjacency lists (Chapters 2.3β3.1) -
Use
queueandstackfrom STL (Chapter 3.1, 3.5) - Work with 2D arrays and grid traversal (Chapter 2.3)
- Understand basic nested loops (Chapter 2.2)
-
Use
priority_queue(Chapter 3.1) β needed for Chapter 5.4 (Dijkstra)
Tips for This Part
- Chapter 5.1 is mostly setup β read it to understand graph representation, but the real algorithms start in Chapter 5.2.
- Chapter 5.2 (BFS) is one of the most important chapters for USACO Silver. Grid BFS appears in roughly 1/3 of Silver problems.
- The
dist[v] == -1pattern for unvisited nodes in BFS is the key. Never mark visited when you pop β always when you push. - Chapter 5.3's Union-Find is faster to code than BFS for connectivity questions. Memorize the 15-line template β you'll use it constantly.
- Chapter 5.4 (Dijkstra) is essential for weighted shortest path problems. Use
priority_queue<pair<int,int>>with the standard template β it's the most common Silver/Gold graph algorithm.
π‘ Key Insight: Most USACO graph problems are actually grid problems in disguise. A grid cell (r,c) becomes a graph node; adjacent cells become edges. BFS on this implicit graph finds shortest paths.
π USACO Tip: Whenever you see "shortest path," "minimum steps," or "fewest moves" in a problem, think BFS immediately. Whenever you see "are these connected?" or "how many groups?", think DSU.