Cycle Detection in Graphs – Complete Detailed Examples

With Step-by-Step, Diagrams, DFS, BFS, Union-Find, and Code

---

1. What is a Cycle?

A cycle is a path in a graph that starts and ends at the same vertex with no repeated vertices (except start/end).

A → B → C → A  → Cycle

---

2. Types of Graphs

Graph Type	Cycle Detection Method
Undirected	DFS (parent check)
Directed	DFS (recursion stack / color)
Weighted	Same as above

---

3. Cycle Detection Methods

Method	Graph Type	Time
DFS (Parent)	Undirected	O(V + E)
DFS (Color / Recursion Stack)	Directed	O(V + E)
BFS (Topological Sort)	Directed	O(V + E)
**Union-Find (...
Kruskal)	Undirected	O(E log E)

---

4. EXAMPLE 1: Undirected Graph – DFS with Parent

Graph

    0
   / \
  1---2
   \ /
    3

Edges: (0-1), (0-2), (1-2), (1-3), (2-3)

---

Step-by-Step DFS

visited[] = {0}
parent[] = {-1}

Step	Call	Node	Neighbor	Visited?	Parent?	Action
1	DFS(0)	0	1	No	-	Visit 1, parent=0
2	DFS(1)	1	0	Yes	parent	Skip
3		1	2	No	-	Visit 2, parent=1
4	DFS(2)	2	0	Yes	not parent	Skip
5		2	1	Yes	parent	Skip
6		2	3	No	-	Visit 3, parent=2
7	DFS(3)	3	1	Yes	not parent	CYCLE! (3→1)
8		3	2	Yes	parent	Skip

Cycle Found: 1 → 2 → 3 → 1

---

Code (Undirected)

int hasCycleDFS(int u, int parent, int visited[]) {
    visited[u] = 1;
    for (Node* v = head[u]; v != NULL; v = v->next) {
        int neighbor = v->vertex;
        if (!visited[neighbor]) {
            if (hasCycleDFS(neighbor, u, visited))
                return 1;
        }
        else if (neighbor != parent) {
            return 1;  // Back edge to non-parent
        }
    }
    return 0;
}

---

5. EXAMPLE 2: Directed Graph – DFS with Recursion Stack

Graph (DAG → No Cycle)

0 → 1 → 3
 \ → 2 → 4

Graph with Cycle

0 → 1 → 2
 ^   /
  \ /
   3

Cycle: 0 → 1 → 2 → 3 → 0

---

Color Coding

Color	Meaning
WHITE	Not visited
GRAY	Visiting (in recursion stack)
BLACK	Finished

---

Step-by-Step

color[] = {WHITE}

Step	Call	Node	Neighbor	Color	Action
1	DFS(0)	0	1	WHITE	Visit 1 → GRAY
2	DFS(1)	1	2	WHITE	Visit 2 → GRAY
3	DFS(2)	2	3	WHITE	Visit 3 → GRAY
4	DFS(3)	3	0	GRAY	CYCLE! (3→0 in stack)
5		3	...	-	Backtrack

---

Code (Directed)

#define WHITE 0
#define GRAY 1
#define BLACK 2

int color[MAX];

int hasCycleDirected(int u) {
    color[u] = GRAY;  // Visiting
    for (Node* v = head[u]; v != NULL; v = v->next) {
        int neighbor = v->vertex;
        if (color[neighbor] == GRAY)
            return 1;  // Back edge to GRAY
        if (color[neighbor] == WHITE && hasCycleDirected(neighbor))
            return 1;
    }
    color[u] = BLACK;  // Done
    return 0;
}

---

6. EXAMPLE 3: Directed Graph – Topological Sort (BFS)

If topological sort possible → No cycle
Else → Cycle exists

Kahn’s Algorithm

1. Compute in-degree of all nodes
2. Start with nodes with in-degree 0
3. Remove node → reduce in-degree of neighbors
4. If all nodes processed → No cycle

---

Graph with Cycle

0 → 1 → 2
 ^   /
  \ /
   3

Node	In-degree
0	1
1	1
2	1
3	1

→ No node with in-degree 0 → Cycle!

---

Code (Kahn’s)

int inDegree[MAX];
Queue q;

int hasCycleBFS() {
    int count = 0;
    for (int i = 0; i < V; i++)
        if (inDegree[i] == 0)
            enqueue(&q, i);

    while (!isEmpty(&q)) {
        int u = dequeue(&q);
        count++;
        for (Node* v = head[u]; v != NULL; v = v->next) {
            inDegree[v->vertex]--;
            if (inDegree[v->vertex] == 0)
                enqueue(&q, v->vertex);
        }
    }
    return count != V;  // If not all visited → cycle
}

---

7. EXAMPLE 4: Undirected – Union-Find (Kruskal)

Used in MST
If adding edge connects same parent → Cycle

Graph

0 -- 1
|    |
2 -- 3

Edges: (0-1), (0-2), (1-3), (2-3)

---

Union-Find Steps

Edge	Find(0)	Find(1)	Same?	Action
0-1	0	1	No	Union(0,1)
0-2	0	2	No	Union(0,2)
1-3	0	3	No	Union(0,3)
2-3	0	0	Yes	CYCLE!

---

Code

int parent[MAX];

int find(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

int hasCycleUnionFind(Edge edges[], int E) {
    for (int i = 0; i < V; i++) parent[i] = i;
    for (int i = 0; i < E; i++) {
        int x = find(edges[i].u);
        int y = find(edges[i].v);
        if (x == y) return 1;
        parent[x] = y;
    }
    return 0;
}

---

8. Visual Summary

Graph	Method	Cycle?	Path
Undirected triangle	DFS	Yes	1→2→0→1
Directed loop	DFS Color	Yes	0→1→2→3→0
DAG	Topo Sort	No	All processed
Square	Union-Find	Yes	2→3 already connected

---

9. Comparison Table

Method	Graph	Space	Best For
DFS (Parent)	Undirected	O(V)	Simple
DFS (Color)	Directed	O(V)	Standard
BFS (Kahn)	Directed	O(V)	Topo sort
Union-Find	Undirected	O(V)	MST

---

10. Full Working Code (All Methods)

#include <stdio.h>
#include <stdlib.h>

#define MAX 100
#define WHITE 0
#define GRAY 1
#define BLACK 2

// Adjacency List
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;
Node* head[MAX];

// DFS Undirected
int visited[MAX];
int hasCycleUndirected(int u, int parent) {
    visited[u] = 1;
    for (Node* v = head[u]; v; v = v->next) {
        if (!visited[v->vertex]) {
            if (hasCycleUndirected(v->vertex, u)) return 1;
        } else if (v->vertex != parent) {
            return 1;
        }
    }
    return 0;
}

// DFS Directed
int color[MAX];
int hasCycleDirected(int u) {
    color[u] = GRAY;
    for (Node* v = head[u]; v; v = v->next) {
        if (color[v->vertex] == GRAY) return 1;
        if (color[v->vertex] == WHITE && hasCycleDirected(v->vertex)) return 1;
    }
    color[u] = BLACK;
    return 0;
}

// Union-Find
int parent[MAX];
int find(int x) { return parent[x] == x ? x : (parent[x] = find(parent[x])); }
int hasCycleUF(int edges[][2], int E) {
    for (int i = 0; i < MAX; i++) parent[i] = i;
    for (int i = 0; i < E; i++) {
        int x = find(edges[i][0]), y = find(edges[i][1]);
        if (x == y) return 1;
        parent[x] = y;
    }
    return 0;
}

int main() {
    // Build graph...
    printf("Cycle: %s\n", hasCycleUndirected(0, -1) ? "Yes" : "No");
    return 0;
}

---

11. Practice Problems

1. Detect cycle in undirected graph with 5 nodes
2. Find cycle path (print nodes)
3. Check if removing one edge makes graph acyclic
4. Detect cycle in directed graph with back edge
5. Use BFS to find cycle in directed graph
6. Count number of cycles

---

12. Key Takeaways

Insight
Undirected: Use parent to avoid false cycle
Directed: Use GRAY to detect back edge
Union-Find: Best for edge-by-edge processing
Topological Sort fails → Cycle
All methods O(V + E)
Cycle = Back edge in DFS

---

End of Cycle Detection Examples