Cycle Detection in Undirected Graph in DSA C - Build from Scratch

Cycle Detection in Undirected Graph

📖 Scenario: Imagine you are working on a network system where devices are connected by cables. You want to check if there is any loop in the connections because loops can cause problems in communication.

🎯 Goal: You will build a program in C to detect if there is a cycle (loop) in an undirected graph representing the network connections.

📋 What You'll Learn

Create an adjacency list to represent the graph

Use a helper array to track visited nodes

Implement a recursive function to detect cycles using Depth First Search (DFS)

Print whether a cycle exists or not

💡 Why This Matters

🌍 Real World

Cycle detection is important in network design, deadlock detection in operating systems, and verifying dependencies in software projects.

💼 Career

Understanding graph traversal and cycle detection is essential for software engineers working on networking, databases, and complex system design.

1

Create the graph adjacency list

Create an integer variable V and set it to 5 for the number of vertices. Then create an array of integer pointers called graph with size V to represent adjacency lists. Initialize the adjacency lists for the following edges: (0-1), (1-2), (2-3), (3-4), (4-1).

DSA C

# Create integer variable V and set it to 5
# Create adjacency list array graph with size V
# Initialize adjacency lists for edges (0-1), (1-2), (2-3), (3-4), (4-1)

Hint

Use an array of integer pointers for adjacency lists. Use a helper function to add edges in both directions because the graph is undirected.

2

Create visited array for tracking nodes

Create an integer array called visited of size V and initialize all elements to 0. This array will track if a node has been visited during traversal.

DSA C

#include 
#include 

int V = 5;

int* graph[5];
int graph_sizes[5] = {0};

void add_edge(int u, int v) {
    graph[u] = realloc(graph[u], (graph_sizes[u] + 1) * sizeof(int));
    graph[u][graph_sizes[u]] = v;
    graph_sizes[u]++;
}

int main() {
    for (int i = 0; i < V; i++) {
        graph[i] = NULL;
        graph_sizes[i] = 0;
    }
    add_edge(0, 1);
    add_edge(1, 0);
    add_edge(1, 2);
    add_edge(2, 1);
    add_edge(2, 3);
    add_edge(3, 2);
    add_edge(3, 4);
    add_edge(4, 3);
    add_edge(4, 1);
    add_edge(1, 4);

    // Create visited array and initialize to 0
    int visited[5] = {0};

    return 0;
}

Hint

Use an integer array with size equal to the number of vertices. Initialize all elements to zero to mark all nodes as unvisited.

3

Implement DFS function to detect cycle

Write a recursive function called dfs that takes three integer parameters: current node, parent node, and the visited array. The function returns 1 if a cycle is found and 0 otherwise. Use the adjacency list graph and graph_sizes to visit neighbors. Mark current as visited. For each neighbor, if it is not visited, recursively call dfs with neighbor as current and current as parent. If a neighbor is visited and is not the parent, return 1 for cycle detected. Return 0 if no cycle found.

DSA C

#include 
#include 

int V = 5;

int* graph[5];
int graph_sizes[5] = {0};

void add_edge(int u, int v) {
    graph[u] = realloc(graph[u], (graph_sizes[u] + 1) * sizeof(int));
    graph[u][graph_sizes[u]] = v;
    graph_sizes[u]++;
}

int dfs(int current, int parent, int visited[]) {
    // Your code here
}

int main() {
    for (int i = 0; i < V; i++) {
        graph[i] = NULL;
        graph_sizes[i] = 0;
    }
    add_edge(0, 1);
    add_edge(1, 0);
    add_edge(1, 2);
    add_edge(2, 1);
    add_edge(2, 3);
    add_edge(3, 2);
    add_edge(3, 4);
    add_edge(4, 3);
    add_edge(4, 1);
    add_edge(1, 4);

    int visited[5] = {0};

    return 0;
}

Hint

Mark the current node as visited. For each neighbor, if not visited, call dfs recursively. If visited and not parent, cycle found.

4

Detect cycle and print result

In main, create a variable has_cycle and set it to 0. Use a for loop with variable i from 0 to V - 1. If visited[i] is 0, call dfs(i, -1, visited). If it returns 1, set has_cycle to 1 and break the loop. After the loop, print "Cycle detected" if has_cycle is 1, else print "No cycle detected".

DSA C

#include 
#include 

int V = 5;

int* graph[5];
int graph_sizes[5] = {0};

void add_edge(int u, int v) {
    graph[u] = realloc(graph[u], (graph_sizes[u] + 1) * sizeof(int));
    graph[u][graph_sizes[u]] = v;
    graph_sizes[u]++;
}

int dfs(int current, int parent, int visited[]) {
    visited[current] = 1;
    for (int i = 0; i < graph_sizes[current]; i++) {
        int neighbor = graph[current][i];
        if (!visited[neighbor]) {
            if (dfs(neighbor, current, visited)) {
                return 1;
            }
        } else if (neighbor != parent) {
            return 1;
        }
    }
    return 0;
}

int main() {
    for (int i = 0; i < V; i++) {
        graph[i] = NULL;
        graph_sizes[i] = 0;
    }
    add_edge(0, 1);
    add_edge(1, 0);
    add_edge(1, 2);
    add_edge(2, 1);
    add_edge(2, 3);
    add_edge(3, 2);
    add_edge(3, 4);
    add_edge(4, 3);
    add_edge(4, 1);
    add_edge(1, 4);

    int visited[5] = {0};

    // Detect cycle and print result
    int has_cycle = 0;
    for (int i = 0; i < V; i++) {
        if (visited[i] == 0) {
            if (dfs(i, -1, visited)) {
                has_cycle = 1;
                break;
            }
        }
    }
    if (has_cycle) {
        printf("Cycle detected\n");
    } else {
        printf("No cycle detected\n");
    }

    return 0;
}

Hint

Loop through all nodes. If not visited, call dfs. If dfs returns 1, print "Cycle detected". Otherwise, print "No cycle detected".

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