Graphs in Depth roadmap
From flood fill on a grid to bridges, shortest paths and spanning trees.
For: Comfortable with BFS and DFS, want graphs to stop being the weak spot
Graphs
Traverse connected structures: islands, components, shortest hops in a grid.
- Paint Bucket Fill
- Number of Islands
- Max Area of Island
- Clone Graph
- Rotting Oranges
- Surrounded Regions
- Pacific Atlantic Water Flow
- Two Room Split
- Teleporter Maze
- Word Ladder
- Keys and Doors
- Escape the Flood
- Critical Cables
- Shortest Path in Binary Matrix
- Open the Lock
- Safest Gallery Walk
- Courier All Stops
- Bus Routes
- One-Way Districts
- Meeting Village
- Three Bucket Pours
- Number of Enclaves
- As Far from Land as Possible
- Zero-One Matrix
- Walls and Gates
- Number of Closed Islands
- Find the Town Judge
- Find if Path Exists in Graph
- Is Graph Bipartite?
- Possible Bipartition
- Minimum Genetic Mutation
- Jump Game III
- Snakes and Ladders
- Shortest Path Visiting All Nodes
- Reconstruct Itinerary
- Word Ladder II
Topological Sort
Order tasks by their dependencies and detect cycles.
- Course Schedule
- Project Finish Time
- Lexicographic Build Order
- Alien Dictionary
- Course Schedule II
- Recipe Production
- Tournament Rankings
- Critical Steps
- Parallel Courses
- Minimum Height Trees
Union-Find
Track which items are connected with near-constant-time merges and lookups.
- Number of Connected Components in an Undirected Graph
- Graph Valid Tree
- Redundant Connection
- Longest Lit Stretch
- Ratio Chains
- Fence Painting
- Number of Provinces
- Accounts Merge
- Convoy Reachable Towns
- Satisfiability of Equality Equations
- Most Stones Removed with Same Row or Column
- Smallest String With Swaps
Shortest Paths
Dijkstra and Bellman-Ford for weighted graphs.
- Network Delay Time
- Ferry Hops
- Cheapest Flights Within K Stops
- Toll Road Coupon
- Path With Minimum Effort
- Swim in Rising Water
- Spell Shift Ladder
- Metro Line Changes
- Electric Van Charging
- Path with Maximum Probability
- Find the City with the Smallest Number of Neighbours
- Minimum Cost to Reach Destination in Time
Minimum Spanning Tree
Connect every node at minimum total cost with Kruskal or Prim.