Cycle Detection in Undirected Graph in DSA C

Mental Model

We want to find if there is a loop in the graph where you can start at one node and come back to it by following edges without repeating the same edge backwards.

Analogy: Imagine walking on city streets (edges) between intersections (nodes). A cycle means you can start at one intersection, walk through some streets, and return to the same intersection without retracing your steps backwards on the same street.

0 -> 1 -> 2
↑         ↓
4 ← 3 ←---

Dry Run Walkthrough

Input: Graph with edges: 0-1, 1-2, 2-3, 3-4, 4-0 (forming a cycle)

Goal: Detect if the graph contains a cycle

Step 1: Start DFS from node 0, mark 0 visited

Visited: {0}
Stack: [0]

Why: We begin exploring from node 0 to find cycles

Step 2: From 0, visit neighbor 1, mark 1 visited

Visited: {0,1}
Stack: [0,1]

Why: Explore neighbors to find cycles

Step 3: From 1, visit neighbor 2, mark 2 visited

Visited: {0,1,2}
Stack: [0,1,2]

Why: Continue deeper to find cycle

Step 4: From 2, visit neighbor 3, mark 3 visited

Visited: {0,1,2,3}
Stack: [0,1,2,3]

Why: Keep exploring neighbors

Step 5: From 3, visit neighbor 4, mark 4 visited

Visited: {0,1,2,3,4}
Stack: [0,1,2,3,4]

Why: Explore last neighbor

Step 6: From 4, neighbor 0 is visited and not parent, cycle detected

Cycle found at node 4 pointing back to 0

Why: Back edge to visited node not parent means cycle

Result:

Cycle detected in the graph

Annotated Code

DSA C

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

#define MAX_NODES 100

// Graph represented as adjacency list
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

Node* graph[MAX_NODES];
bool visited[MAX_NODES];

Node* createNode(int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

void addEdge(int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = graph[src];
    graph[src] = newNode;

    newNode = createNode(src);
    newNode->next = graph[dest];
    graph[dest] = newNode;
}

bool dfs(int vertex, int parent) {
    visited[vertex] = true; // mark current node visited
    Node* temp = graph[vertex];
    while (temp != NULL) {
        int adjVertex = temp->vertex;
        if (!visited[adjVertex]) {
            if (dfs(adjVertex, vertex)) {
                return true; // cycle found in deeper call
            }
        } else if (adjVertex != parent) {
            return true; // visited node not parent means cycle
        }
        temp = temp->next; // move to next neighbor
    }
    return false; // no cycle found from this path
}

bool isCycle(int n) {
    for (int i = 0; i < n; i++) {
        visited[i] = false; // reset visited
    }
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            if (dfs(i, -1)) {
                return true; // cycle detected
            }
        }
    }
    return false; // no cycle in any component
}

int main() {
    int n = 5; // number of nodes
    for (int i = 0; i < n; i++) {
        graph[i] = NULL;
    }

    addEdge(0, 1);
    addEdge(1, 2);
    addEdge(2, 3);
    addEdge(3, 4);
    addEdge(4, 0); // adding edge to form cycle

    if (isCycle(n)) {
        printf("Cycle detected in the graph\n");
    } else {
        printf("No cycle detected in the graph\n");
    }
    return 0;
}

visited[vertex] = true; // mark current node visited

mark current node as visited to track traversal

if (!visited[adjVertex]) { if (dfs(adjVertex, vertex)) { return true; } }

visit unvisited neighbor recursively to detect cycle

else if (adjVertex != parent) { return true; }

detect back edge to visited node not parent means cycle

for (int i = 0; i < n; i++) { if (!visited[i]) { if (dfs(i, -1)) { return true; } } }

check all graph components for cycles

Output

Cycle detected in the graph

Complexity Analysis

Time: O(V + E) because each vertex and edge is visited once during DFS

Space: O(V + E) for adjacency list storage and O(V) for recursion stack and visited array

vs Alternative: Compared to adjacency matrix O(V^2), adjacency list is more efficient for sparse graphs

Edge Cases

Empty graph (no nodes)

No cycle detected as there are no edges

DSA C

for (int i = 0; i < n; i++) { if (!visited[i]) { if (dfs(i, -1)) { return true; } } }

Graph with single node and no edges

No cycle detected because no edges exist

DSA C

for (int i = 0; i < n; i++) { if (!visited[i]) { if (dfs(i, -1)) { return true; } } }

Graph with multiple disconnected components

Cycle detection runs on each component separately

DSA C

for (int i = 0; i < n; i++) { if (!visited[i]) { if (dfs(i, -1)) { return true; } } }

When to Use This Pattern

When you need to check if an undirected graph has loops, use DFS with parent tracking to detect back edges indicating cycles.

Common Mistakes

Mistake: Not checking if the visited neighbor is the parent node, causing false cycle detection
Fix: Add condition to ignore the edge back to parent node during DFS

Summary

Detects if an undirected graph contains a cycle by DFS traversal with parent tracking.

Use when you want to know if a graph has loops that can cause repeated paths.

The key insight is that a visited neighbor that is not the parent means a cycle exists.