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

Cycle Detection in Directed Graph

📖 Scenario: Imagine you are working on a task scheduler that runs jobs based on dependencies. If there is a cycle in the dependencies, the scheduler will get stuck forever. You need to detect if such a cycle exists in the directed graph of job dependencies.

🎯 Goal: Build a program in C that detects if a directed graph has a cycle using Depth First Search (DFS).

📋 What You'll Learn

Create a graph using adjacency lists with 4 nodes and specific edges

Create arrays to track visited nodes and recursion stack

Implement a DFS function to detect cycles

Print whether the graph contains a cycle or not

💡 Why This Matters

🌍 Real World

Cycle detection is crucial in task scheduling, deadlock detection, and dependency resolution in software and systems.

💼 Career

Understanding graph cycle detection is important for roles in software development, systems engineering, and data analysis where dependency management is key.

1

Create the Directed Graph

Create an adjacency list for a directed graph with 4 nodes (0 to 3). Add edges: 0->1, 1->2, 2->3, and 3->1. Use an array of pointers to integer arrays called graph and an array graphSize to store the number of neighbors for each node.

DSA C

# Create the adjacency list arrays for 4 nodes
// Your code here

Hint

Use arrays to store neighbors for each node and assign them to graph array.

2

Create Visited and Recursion Stack Arrays

Create two integer arrays called visited and recStack of size 4, initialized to 0. These will track visited nodes and nodes in the current recursion stack.

DSA C

#include 
#include 

int main() {
    int graphSize[4] = {1, 1, 1, 1};
    int* graph[4];

    int neighbors0[] = {1};
    int neighbors1[] = {2};
    int neighbors2[] = {3};
    int neighbors3[] = {1};

    graph[0] = neighbors0;
    graph[1] = neighbors1;
    graph[2] = neighbors2;
    graph[3] = neighbors3;

    // Create visited and recStack arrays initialized to 0
    int visited[4] = {0};
    int recStack[4] = {0};

    // Your code here

    return 0;
}

Hint

Initialize both arrays with zeros to mark all nodes as unvisited and not in recursion stack.

3

Implement DFS Function to Detect Cycle

Write a function int dfs(int node, int* visited, int* recStack, int** graph, int* graphSize) that returns 1 if a cycle is detected starting from node, otherwise 0. Use recursion and check neighbors. Mark visited[node] and recStack[node] as 1 when visiting, and reset recStack[node] to 0 before returning. Use a for loop with int i to iterate neighbors.

DSA C

#include 
#include 

int dfs(int node, int* visited, int* recStack, int** graph, int* graphSize) {
    // Implement DFS to detect cycle
    // Your code here
}

int main() {
    int graphSize[4] = {1, 1, 1, 1};
    int* graph[4];

    int neighbors0[] = {1};
    int neighbors1[] = {2};
    int neighbors2[] = {3};
    int neighbors3[] = {1};

    graph[0] = neighbors0;
    graph[1] = neighbors1;
    graph[2] = neighbors2;
    graph[3] = neighbors3;

    int visited[4] = {0};
    int recStack[4] = {0};

    return 0;
}

Hint

Mark the node visited and in recursion stack. For each neighbor, if not visited, recurse. If neighbor is in recursion stack, cycle found.

4

Detect Cycle and Print Result

In main, use a for loop with int i from 0 to 3. If visited[i] is 0, call dfs(i, visited, recStack, graph, graphSize). If it returns 1, print "Cycle detected" and exit. If no cycle found after loop, print "No cycle detected".

DSA C

#include 
#include 

int dfs(int node, int* visited, int* recStack, int** graph, int* graphSize) {
    if (!visited[node]) {
        visited[node] = 1;
        recStack[node] = 1;

        for (int i = 0; i < graphSize[node]; i++) {
            int neighbor = graph[node][i];
            if (!visited[neighbor] && dfs(neighbor, visited, recStack, graph, graphSize)) {
                return 1;
            } else if (recStack[neighbor]) {
                return 1;
            }
        }
    }
    recStack[node] = 0;
    return 0;
}

int main() {
    int graphSize[4] = {1, 1, 1, 1};
    int* graph[4];

    int neighbors0[] = {1};
    int neighbors1[] = {2};
    int neighbors2[] = {3};
    int neighbors3[] = {1};

    graph[0] = neighbors0;
    graph[1] = neighbors1;
    graph[2] = neighbors2;
    graph[3] = neighbors3;

    int visited[4] = {0};
    int recStack[4] = {0};

    // Detect cycle and print result
    // Your code here

    return 0;
}

Hint

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