DSA Sheet - Day 27 Graphs
🌐 DSA Sheet – Day 27: Advanced Graphs (MST & Shortest Paths)
This section covers advanced graph algorithms including Minimum Spanning Trees and shortest path techniques — commonly asked in high-level interviews.
📊 Progress Tracker
Progress: 0 / 7 Completed
| Done | Problem | Practice | Level | Companies |
|---|---|---|---|---|
| Kruskal's Algorithm (MST) | Solve | Hard | Amazon, DE Shaw | |
| Prim's Algorithm (MST) | Solve | Hard | Amazon, Uber | |
| Rotting Oranges | Solve | Medium | Amazon, Meta | |
| Clone Graph | Solve | Medium | Google, Meta | |
| Floyd Warshall Algorithm | Solve | Hard | Google, Uber | |
| Bellman Ford Algorithm | Solve | Hard | Amazon, Microsoft | |
| 01 Matrix | Solve | Medium | Amazon |
🧠 Key Approaches
- Kruskal: Sort edges + DSU (Union-Find)
- Prim: Min heap + greedy expansion
- Rotting Oranges: Multi-source BFS
- Clone Graph: BFS/DFS + hashmap
- Floyd Warshall: All-pairs shortest path (DP)
- Bellman Ford: Relax edges V-1 times (handles negative weights)
- 01 Matrix: Multi-source BFS
⚡ Quick Cheatsheet
Kruskal (Union-Find)
// sort edges by weight
// use DSU to avoid cycles
Prim's Algorithm
priority_queue, vector>, greater<>> pq;
// {weight, node}
Bellman Ford
for(int i = 0; i < n-1; i++){
for(auto edge : edges){
// relax edges
}
}
Floyd Warshall
for(int k = 0; k < n; k++)
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
🔥 Pro Tip
Choose the right algorithm fast:
- MST problem? → Kruskal or Prim
- Negative weights? → Bellman Ford
- All-pairs shortest path? → Floyd Warshall
- Grid BFS? → Multi-source BFS