DSA Sheet - Day 25 Graphs
🌐 DSA Sheet – Day 25: Graphs (BFS, DFS, Cycle Detection)
Graphs are one of the most important topics for interviews. This section covers traversal techniques and cycle detection — the foundation for advanced problems.
📊 Progress Tracker
Progress: 0 / 6 Completed
| Done | Problem | Practice | Level | Companies |
|---|---|---|---|---|
| DFS (Depth First Search) | Solve | Medium | Amazon, Samsung | |
| BFS (Breadth First Search) | Solve | Medium | Flipkart, SAP | |
| Cycle Detection (Undirected - BFS) | Solve | Medium | Microsoft, Oracle | |
| Cycle Detection (Undirected - DFS) | Solve | Medium | Google, Flipkart | |
| Cycle Detection (Directed - DFS) | Solve | Medium | Amazon, Google | |
| Cycle Detection (Directed - BFS / Kahn’s Algorithm) | Solve | Medium | Amazon, Microsoft |
🧠 Key Approaches
- DFS: Recursive traversal using visited array
- BFS: Queue-based traversal (level by level)
- Undirected Cycle (BFS): Track parent node
- Undirected Cycle (DFS): Check visited + parent
- Directed Cycle (DFS): Use recursion stack
- Directed Cycle (BFS): Kahn’s Algorithm (Topological Sort)
⚡ Quick Cheatsheet
DFS Traversal
void dfs(int node){
vis[node] = 1;
for(auto it : adj[node]){
if(!vis[it]) dfs(it);
}
}
BFS Traversal
queue q;
q.push(start);
vis[start] = 1;
while(!q.empty()){
int node = q.front(); q.pop();
for(auto it : adj[node]){
if(!vis[it]){
vis[it] = 1;
q.push(it);
}
}
}
Directed Cycle Detection (DFS)
bool dfs(int node){
vis[node] = path[node] = 1;
for(auto it : adj[node]){
if(!vis[it] && dfs(it)) return true;
else if(path[it]) return true;
}
path[node] = 0;
return false;
}
🔥 Pro Tip
Recognize patterns instantly:
- Traversal problem? → BFS / DFS
- Cycle detection? → DFS (directed) or BFS/DFS (undirected)
- Course scheduling? → Kahn’s Algorithm