Cycle Detection in Graphs – Complete Detailed Examples

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

Cycle Detection in Graphs – Complete Detailed Examples

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

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

Last updated: Nov 12, 2025

Cycle Detection in Graphs – Complete Detailed Examples

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

Cycle Detection in Graphs – Complete Detailed Examples

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

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

Last updated: Nov 12, 2025