12. Graphs
🧠Graph Strategy
- Model the Problem: Is it a Grid? A directed dependency (Topo)? A weighted network (Dijkstra/MST)?
- Choose Algorithm:
- Shortest Path (Unweighted) -> BFS
- Shortest Path (Weighted) -> Dijkstra
- Connectivity/Groups -> DSU or DFS
- Dependencies -> Topological Sort
- Complexity: \(O(V+E)\) for traversal, \(O(E \log V)\) for Dijkstra/Prim.
🟢 Traversal (DFS/BFS)
- First Depth First Search
- Path In Directed Graph
- Cycle In Directed Graph
- Cycle In Undirected Graph
- Clone Graph
- Valid Path
🟡 Grid & Multi-Source BFS
- Number Of Islands
- Black Shapes
- Rotten Oranges
- Distance Of Nearest Cell
- Knight On Chess Board
- Shortest Distance In A Maze
- Capture Regions On Board
- Another BFS
🟠Topological Sort & Bipartite
- Topological Sort
- Possibility Of Finishing
- Check Bipartite Graph
- Coloring A Cycle Graph
- Poisonous Graph
🔴 MST & DSU (Disjoint Set)
- Commutable Islands
- Batches
- Construction Cost
- Damaged Roads
- Construct Roads
- Edge In MST
- Gym Trainer
- Cows And Snacks