DSA Sheet - Day 26 Graphs
🌐 DSA Sheet – Day 26: Graphs (Topological Sort & Shortest Path)
This section focuses on graph ordering and shortest path algorithms — extremely important for real interview problems like scheduling and routing.
📊 Progress Tracker
Progress: 0 / 6 Completed
| Done | Problem | Practice | Level | Companies |
|---|---|---|---|---|
| Topological Sort (DFS) | Solve | Medium | Flipkart, Morgan Stanley | |
| Flood Fill Algorithm | Solve | Easy | Microsoft, Apple | |
| Topological Sort (BFS / Kahn’s) | Solve | Medium | Microsoft, Accolite | |
| Course Schedule II | Solve | Medium | Amazon, Meta | |
| Cheapest Flights within K Stops | Solve | Medium | Amazon, Oracle | |
| Dijkstra's Algorithm | Solve | Medium | Amazon, Google |
🧠 Key Approaches
- Topo Sort (DFS): Postorder DFS + stack
- Flood Fill: BFS/DFS traversal on grid
- Topo Sort (BFS): Kahn’s Algorithm using indegree
- Course Schedule II: Return valid topo order
- Cheapest Flights: BFS / Modified Dijkstra (limit stops)
- Dijkstra: Min heap + distance relaxation
⚡ Quick Cheatsheet
Topological Sort (DFS)
void dfs(int node){
vis[node] = 1;
for(auto it : adj[node])
if(!vis[it]) dfs(it);
st.push(node);
}
Kahn’s Algorithm (BFS Topo)
queue q;
for(int i = 0; i < n; i++)
if(indegree[i] == 0) q.push(i);
while(!q.empty()){
int node = q.front(); q.pop();
for(auto it : adj[node]){
indegree[it]--;
if(indegree[it] == 0) q.push(it);
}
}
Dijkstra’s Algorithm
priority_queue, vector>, greater<>> pq;
pq.push({0, src});
while(!pq.empty()){
auto [dist, node] = pq.top(); pq.pop();
// relax edges
}
🔥 Pro Tip
Identify instantly:
- Dependencies / ordering? → Topological Sort
- Shortest path (weighted)? → Dijkstra
- Grid problems? → BFS / DFS
- Limited stops / constraints? → Modified BFS / Dijkstra