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.

Practice

1. What is the main idea behind detecting a cycle in an undirected graph using DFS?

easy

A. If the graph is disconnected, it contains a cycle.

B. If all nodes are visited exactly once, the graph has a cycle.

C. If we visit a node that is already visited and is not the parent, a cycle exists.

D. If the graph has more edges than nodes, it always has a cycle.

Solution

1. Step 1: Understand DFS traversal in undirected graph

   DFS visits nodes and tracks the parent node to avoid false cycle detection.

2. Step 2: Detect cycle condition

   If a visited node is found that is not the parent, it means a back edge exists, indicating a cycle.

3. Final Answer:

   If we visit a node that is already visited and is not the parent, a cycle exists. -> Option C

4. Quick Check:

   Cycle detection in undirected graph = check visited node not parent [OK]

Hint: Check visited neighbors excluding parent to find cycles [OK]

Common Mistakes:

• Ignoring the parent node in cycle check
• Assuming disconnected graph always has cycles
• Confusing edge count with cycle presence

2. Which of the following is the correct function signature in C for DFS used in cycle detection in an undirected graph?

easy

A. bool dfs(int node, int parent, int visited[], int graph[][100], int n)

B. int dfs(int node, int visited[], int graph[][100])

C. void dfs(int node, int graph[][100], int visited[])

D. int dfs(int node, int parent, int graph[][100])

Solution

1. Step 1: Identify parameters needed for DFS cycle detection

   We need current node, parent node, visited array, adjacency matrix, and number of nodes.

2. Step 2: Match function signature with parameters

   bool dfs(int node, int parent, int visited[], int graph[][100], int n) includes all required parameters with correct types and order.

3. Final Answer:

   bool dfs(int node, int parent, int visited[], int graph[][100], int n) -> Option A

4. Quick Check:

   DFS signature includes node, parent, visited, graph, size [OK]

Hint: Include parent parameter to avoid false cycle detection [OK]

Common Mistakes:

• Omitting parent parameter
• Wrong return type for DFS
• Missing graph size parameter

3. Consider the following adjacency matrix for an undirected graph with 4 nodes:

int graph[4][4] = {
  {0, 1, 0, 0},
  {1, 0, 1, 1},
  {0, 1, 0, 0},
  {0, 1, 0, 0}
};

If we run cycle detection using DFS starting from node 0, what will be the output?

medium

A. Cycle detected

B. No cycle detected

C. Runtime error due to invalid indexing

D. Infinite loop

Solution

1. Step 1: Analyze graph edges from adjacency matrix

   Edges: 0-1, 1-2, 1-3. Node 1 connects to nodes 0, 2, 3.

2. Step 2: Check for cycle using DFS

   Starting at 0, DFS visits 1, then 2 and 3. Node 1 connects back to 0 (parent), no cycle there. No back edge to visited non-parent node is found, so no cycle.

3. Final Answer:

   No cycle detected -> Option B

4. Quick Check:

   Graph edges form a tree structure = No cycle [OK]

Hint: Trace DFS and check visited nodes excluding parent [OK]

Common Mistakes:

• Assuming any connected graph has cycle
• Ignoring parent node in cycle check
• Confusing adjacency matrix indexing

4. The following C code snippet is intended to detect a cycle in an undirected graph using DFS. What is the bug?

bool dfs(int node, int parent, int visited[], int graph[][100], int n) {
  visited[node] = 1;
  for (int i = 0; i < n; i++) {
    if (graph[node][i] == 1) {
      if (!visited[i]) {
        if (dfs(i, node, visited, graph, n))
          return true;
      } else if (i != parent) {
        return true;
      }
    }
  }
  return false;
}

medium

A. The visited array is not initialized before calling dfs.

B. The parent parameter is not passed correctly in recursive calls.

C. The graph adjacency matrix is accessed out of bounds.

D. The function should return void, not bool.

Solution

1. Step 1: Check initialization of visited array

   The code snippet does not show visited array initialization, which is required to mark nodes unvisited before DFS.

2. Step 2: Verify other parameters and logic

   Parent is passed correctly, adjacency matrix access is within bounds, and return type bool is appropriate for cycle detection.

3. Final Answer:

   The visited array is not initialized before calling dfs. -> Option A

4. Quick Check:

   Initialize visited[] before DFS to avoid incorrect results [OK]

Hint: Always initialize visited array to zero before DFS [OK]

Common Mistakes:

• Forgetting to initialize visited array
• Passing wrong parent in recursion
• Misusing return type for DFS

5. You have an undirected graph represented by adjacency lists:

0: 1, 2
1: 0, 3
2: 0, 3
3: 1, 2

Using cycle detection with DFS, which nodes form the cycle and why?

hard

A. Nodes 0, 1, 3 form a cycle because 0 connects to 1 and 1 connects to 3.

B. Nodes 0, 2, 3 form a cycle because 0 connects to 2 and 2 connects to 3 which connects back to 0.

C. Nodes 1, 2, 3 form a cycle because 1 connects to 3 and 2 connects to 3.

D. Nodes 0, 1, 2, 3 form a cycle because they form a closed loop through all edges.

Solution

1. Step 1: Analyze adjacency lists for cycles

   Edges: 0-1, 0-2, 1-3, 2-3. These edges connect nodes forming a square shape.

2. Step 2: Identify cycle involving all nodes

   Starting at 0, path 0->1->3->2->0 forms a closed loop including all four nodes, indicating a cycle involving nodes 0,1,2,3.

3. Final Answer:

   Nodes 0, 1, 2, 3 form a cycle because they form a closed loop through all edges. -> Option D

4. Quick Check:

   Cycle includes all nodes forming closed loop [OK]

Hint: Look for closed loops connecting all nodes [OK]

Common Mistakes:

• Identifying partial cycles ignoring full loop
• Confusing connected nodes with cycle nodes
• Missing edges that complete the cycle