Advanced Graphs
Overview
The Graphs category taught BFS/DFS/Union-Find/topo sort. This category adds the weighted variants and a few niche algorithms:
- Eulerian path, visit every edge once (Reconstruct Itinerary, Hierholzer’s).
- Minimum spanning tree (MST), Prim’s (priority queue) or Kruskal’s (sort + union-find).
- Single-source shortest path with non-negative weights, Dijkstra.
- Single-source shortest path with negative weights or bounded hops, Bellman-Ford.
- Dijkstra on implicit graphs, grid “minimum max edge” problems.
Problems
- 332. Reconstruct Itinerary (Hard)
- 1584. Min Cost to Connect All Points (Medium)
- 743. Network Delay Time (Medium)
- 787. Cheapest Flights Within K Stops (Medium)
- 778. Swim in Rising Water (Hard)
Note: 269. Alien Dictionary is sometimes categorized here. This site places it in the Graphs category since it’s a topological-sort variant.
Key patterns unlocked here
- Hierholzer’s algorithm for Eulerian paths, Reconstruct Itinerary.
- Prim’s MST with a priority queue, Min Cost to Connect All Points.
- Dijkstra with heap, Network Delay Time.
- Bellman-Ford with hop limit, Cheapest Flights Within K Stops.
- Modified Dijkstra for min-max edge, Swim in Rising Water.