DSA Graph Cycle Detection

🔁 DSA Graph Cycle Detection – Complete Beginner Guide

(Undirected • Directed • BFS • DFS • Code • Complexity)

Cycle Detection is one of the most asked graph problems in DSA interviews.
A cycle exists if you can start at a node and come back to the same node by following edges.

1️⃣ What is a Cycle in a Graph?

A cycle is a path where:

Start node = End node
Length ≥ 1 edge

Example

2️⃣ Why Cycle Detection is Important

✔ Deadlock detection
✔ Validating graphs (DAG check)
✔ Scheduling problems
✔ Network analysis
✔ Compiler design

3️⃣ Cycle Detection – Based on Graph Type

Graph Type	Method Used
Undirected Graph	DFS / BFS with Parent
Directed Graph	DFS with Recursion Stack
Directed Acyclic Graph	Topological Sort

PART 1: Cycle Detection in Undirected Graph

4️⃣ Undirected Graph – Using DFS

Idea

Use visited[]
Pass parent node
If visited neighbor ≠ parent → cycle

Algorithm (DFS)

Mark current node visited
For each neighbor:
- If not visited → DFS
- If visited & not parent → cycle found

C++ Code (DFS – Undirected)

bool dfs(int node, int parent, vector<int> adj[], vector<bool>& visited) {
    visited[node] = true;

    for(int x : adj[node]) {
        if(!visited[x]) {
            if(dfs(x, node, adj, visited))
                return true;
        }
        else if(x != parent) {
            return true; // cycle detected
        }
    }
    return false;
}

bool dfs(int node, int parent, vector<int> adj[], vector<bool>& visited) {

visited[node] = true;

for(int x : adj[node]) {

if(!visited[x]) {

if(dfs(x, node, adj, visited))

return true;

}

else if(x != parent) {

return true; // cycle detected

}

return false;

}

5️⃣ Undirected Graph – Using BFS

Idea

Queue stores (node, parent)
If visited neighbor ≠ parent → cycle

C++ Code (BFS – Undirected)

#include <queue>

bool bfs(int start, vector<int> adj[], vector<bool>& visited) {
    queue<pair<int,int>> q;
    visited[start] = true;
    q.push({start, -1});

    while(!q.empty()) {
        int node = q.front().first;
        int parent = q.front().second;
        q.pop();

        for(int x : adj[node]) {
            if(!visited[x]) {
                visited[x] = true;
                q.push({x, node});
            }
            else if(x != parent) {
                return true; // cycle
            }
        }
    }
    return false;
}

#include <queue>

bool bfs(int start, vector<int> adj[], vector<bool>& visited) {

queue<pair<int,int>> q;

visited[start] = true;

q.push({start, -1});

while(!q.empty()) {

int node = q.front().first;

int parent = q.front().second;

q.pop();

for(int x : adj[node]) {

if(!visited[x]) {

visited[x] = true;

q.push({x, node});

}

else if(x != parent) {

return true; // cycle

}

return false;

}

PART 2: Cycle Detection in Directed Graph

6️⃣ Directed Graph – Using DFS (Recursion Stack)

Idea

Use two arrays:

visited[] → visited nodes
recStack[] → nodes in current recursion

If a node is visited and in recursion stack → cycle

Algorithm

Mark node visited
Mark node in recursion stack
For each neighbor:
- If not visited → DFS
- If in recursion stack → cycle
Remove node from recursion stack

C++ Code (DFS – Directed)

bool dfs(int node, vector<int> adj[], vector<bool>& visited, vector<bool>& recStack) {
    visited[node] = true;
    recStack[node] = true;

    for(int x : adj[node]) {
        if(!visited[x]) {
            if(dfs(x, adj, visited, recStack))
                return true;
        }
        else if(recStack[x]) {
            return true; // cycle detected
        }
    }

    recStack[node] = false;
    return false;
}

bool dfs(int node, vector<int> adj[], vector<bool>& visited, vector<bool>& recStack) {

visited[node] = true;

recStack[node] = true;

for(int x : adj[node]) {

if(!visited[x]) {

if(dfs(x, adj, visited, recStack))

return true;

}

else if(recStack[x]) {

return true; // cycle detected

}

recStack[node] = false;

return false;

}

7️⃣ Cycle Detection Using Topological Sort

Only for Directed Graph

If topological sort is not possible
Graph contains a cycle

Use Kahn’s Algorithm

8️⃣ Time & Space Complexity

Method	Time	Space
DFS (Undirected)	O(V + E)	O(V)
BFS (Undirected)	O(V + E)	O(V)
DFS (Directed)	O(V + E)	O(V)

9️⃣ Undirected vs Directed – Key Difference

Aspect	Undirected	Directed
Parent needed	✅ Yes	❌ No
Recursion Stack	❌ No	✅ Yes
Edge direction	Both ways	One way

🔟 Common Interview Questions

Q1. How to detect cycle in undirected graph?
👉 DFS/BFS with parent

Q2. How to detect cycle in directed graph?
👉 DFS + recursion stack

Q3. Can BFS detect cycle in directed graph?
👉 No (use Kahn’s algorithm)

Q4. What does recursion stack represent?
👉 Current DFS path

Final Summary

✔ Cycle detection depends on graph type
✔ Undirected → parent check
✔ Directed → recursion stack
✔ Time complexity: O(V + E)
✔ Very common in DSA interviews

DSA Graph Cycle Detection