Chapter 32: DSA Graphs Cycle Detection
DSA Graph Cycle Detection – Let’s understand this topic properly and in depth, like I’m sitting next to you with a whiteboard, drawing graphs step by step, explaining every single detail slowly, comparing both main approaches side by side, showing multiple examples, and most importantly telling you why cycle detection is one of the most frequently asked graph problems in interviews.
What is a Cycle in a Graph?
A cycle exists in a graph when you can start at any vertex, follow some edges, and return to the same starting vertex without repeating any edge (or sometimes without repeating vertices, depending on definition).
In simple words:
If there is a loop that brings you back to where you started, there is a cycle.
Why Cycle Detection is Important
Real-world situations where cycles matter:
| Situation | Why cycle is bad / meaningful |
|---|---|
| Task scheduling / Course prerequisites | Cycle means impossible to complete (circular dependency) |
| Directed Acyclic Graph (DAG) | Many algorithms require no cycles |
| Deadlock detection | Cycle in resource allocation graph → deadlock |
| Infinite loop in state machines | Cycle means system may never terminate |
| Social network analysis | Cycle can indicate tight-knit groups or redundancy |
| Financial transaction graphs | Cycle may indicate money laundering patterns |
Two Main Cases We Need to Handle
- Undirected Graph Cycle Detection
- Directed Graph Cycle Detection
Both are asked very frequently — and they require slightly different logic.
1. Cycle Detection in Undirected Graph
Key idea: A cycle exists if during DFS/BFS traversal, we visit a node that is already visited and it is not the parent of the current node.
Why parent check is needed:
In undirected graph, every edge is bidirectional. So when we go from A → B, we will also have edge B → A. We don’t want to consider this back-edge as a cycle.
Algorithm (DFS-based – most common in interviews)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
DFS(node, parent): mark node as visited for each neighbor in adjacency list of node: if neighbor is not visited: if DFS(neighbor, node) returns true: return true // cycle found in subtree else if neighbor != parent: return true // back edge → cycle found return false // no cycle in this branch |
Example – Undirected Graph with Cycle
Vertices: 0, 1, 2, 3, 4
Edges: 0-1, 1-2, 2-3, 3-0, 2-4
|
0 1 2 3 4 5 6 7 8 |
0 ── 1 │ │ 3 ── 2 ── 4 |
Start DFS from 0
- Visit 0, parent = -1
- Go to 1 (not visited), parent = 0
- Visit 1
- Go to 2 (not visited), parent = 1
- Visit 2
- Go to 3 (not visited), parent = 2
- Visit 3
- Neighbor 0 is visited and ≠ parent 2 → cycle found!
Output: Cycle exists
Code – Undirected Cycle Detection (DFS)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
def hasCycleUndirected(graph, V): visited = [False] * V def dfs(node, parent): visited[node] = True for neighbor in graph[node]: if not visited[neighbor]: if dfs(neighbor, node): return True elif neighbor != parent: return True return False # Handle disconnected components for i in range(V): if not visited[i]: if dfs(i, -1): return True return False |
2. Cycle Detection in Directed Graph
Key difference: In directed graphs, we don’t have automatic back-edges like in undirected. We need to detect if there is a back edge to an ancestor in the current recursion stack.
We need to track two states:
- Visited — node has been visited before
- In recursion stack (or “being visited”) — node is currently in the call stack
Three colors / states method (very common & clear):
- White = not visited
- Gray = being visited (in current recursion stack)
- Black = finished visiting (all descendants processed)
Cycle exists if we try to visit a gray node again.
Algorithm
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
DFS(node): color[node] = GRAY # mark as being visited for neighbor in graph[node]: if color[neighbor] == GRAY: return true # back edge to ancestor → cycle! if color[neighbor] == WHITE: if DFS(neighbor): return true color[node] = BLACK # finished return false |
Example – Directed Graph with Cycle
Vertices: A → B → C → D → B (cycle B→C→D→B)
|
0 1 2 3 4 5 6 7 8 |
A → B → C → D ↑ │ └─────┘ |
DFS from A
- Visit A → GRAY
- Go to B → GRAY
- Go to C → GRAY
- Go to D → GRAY
- D → B, B is GRAY → cycle found!
Code – Directed Cycle Detection (DFS)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
def hasCycleDirected(graph, V): WHITE, GRAY, BLACK = 0, 1, 2 color = [WHITE] * V def dfs(node): color[node] = GRAY for neighbor in graph[node]: if color[neighbor] == GRAY: return True if color[neighbor] == WHITE: if dfs(neighbor): return True color[node] = BLACK return False for i in range(V): if color[i] == WHITE: if dfs(i): return True return False |
DFS vs BFS for Cycle Detection
| Method | Works for Undirected? | Works for Directed? | Notes |
|---|---|---|---|
| DFS | Yes | Yes | Easier to implement, most common |
| BFS | Yes | Yes | More code, less natural for cycle |
Most interviews expect DFS approach — both for directed and undirected.
Summary – Cycle Detection Cheat Sheet
| Graph Type | Main Method | Key Idea | Time Complexity |
|---|---|---|---|
| Undirected | DFS | Back edge to visited node (except parent) | O(V + E) |
| Directed | DFS | Back edge to node in recursion stack (gray node) | O(V + E) |
| Disconnected | Run on every component | Must check all components | O(V + E) |
Would you like to continue with any specific cycle detection topic?
Very natural next steps:
- Step-by-step dry run of both undirected and directed cycle detection
- Cycle detection using BFS (coloring method or parent tracking)
- Detect cycle in directed graph – all possible paths explanation
- Find cycle path (not just existence)
- Topological sort – how it relates to cycle detection
- Union-Find approach for undirected cycle detection
Just tell me which one you want next — I’ll explain it with the same level of detail, visuals, step-by-step clarity, and examples! 😊
