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".