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

Practice

1. What does cycle detection in a directed graph help us find?

easy

A. Whether there is a path that starts and ends at the same node following edge directions

B. The shortest path between two nodes

C. The total number of nodes in the graph

D. The maximum degree of any node

Solution

1. Step 1: Understand cycle in directed graph

   A cycle means a path that starts and ends at the same node following the direction of edges.

2. Step 2: Identify what cycle detection finds

   Cycle detection checks if such a path exists in the graph.

3. Final Answer:

   Whether there is a path that starts and ends at the same node following edge directions -> Option A

4. Quick Check:

   Cycle detection = path starting and ending at same node [OK]

Hint: Cycle means path loops back to start following edges [OK]

Common Mistakes:

• Confusing cycle with shortest path
• Thinking cycle ignores edge directions
• Mixing cycle detection with counting nodes

2. Which of the following is the correct way to declare a visited array for cycle detection in C for a graph with n nodes?

easy

A. int visited = new int[n];

B. int visited[n] = {0};

C. int visited[] = {0};

D. int visited[n];

Solution

1. Step 1: Understand array declaration in C

   In C, to declare an array of size n, use int visited[n]; but it is uninitialized.

2. Step 2: Initialize array to zero

   To initialize all elements to zero, use int visited[n] = {0}; which sets all to zero.

3. Final Answer:

   int visited[n] = {0}; -> Option B

4. Quick Check:

   Array declaration with zero init = int visited[n] = {0}; [OK]

Hint: Use int arr[n] = {0} to initialize all zeros in C [OK]

Common Mistakes:

• Using 'new' keyword which is C++ not C
• Declaring array without size
• Incorrect initialization syntax

3. Consider the following C code snippet for cycle detection in a directed graph using DFS. What will be the output?

void dfs(int node, int visited[], int recStack[], int graph[][3]) {
    visited[node] = 1;
    recStack[node] = 1;
    for (int i = 0; i < 3; i++) {
        int adj = graph[node][i];
        if (adj == -1) continue;
        if (!visited[adj]) dfs(adj, visited, recStack, graph);
        else if (recStack[adj]) printf("Cycle detected\n");
    }
    recStack[node] = 0;
}

int main() {
    int graph[3][3] = {{1, -1, -1}, {2, -1, -1}, {0, -1, -1}};
    int visited[3] = {0}, recStack[3] = {0};
    dfs(0, visited, recStack, graph);
    return 0;
}

medium

A. No output

B. Infinite loop

C. Segmentation fault

D. Cycle detected

Solution

1. Step 1: Analyze graph edges

   Graph edges: 0->1, 1->2, 2->0 form a cycle.

2. Step 2: Trace DFS calls and cycle detection

   DFS visits 0, then 1, then 2. When 2 tries to visit 0 again which is in recursion stack, it prints "Cycle detected".

3. Final Answer:

   Cycle detected -> Option D

4. Quick Check:

   Cycle in graph triggers print "Cycle detected" [OK]

Hint: Cycle prints when node revisited in recursion stack [OK]

Common Mistakes:

• Ignoring recursion stack for cycle detection
• Assuming no output means no cycle
• Confusing visited and recursion stack arrays

4. The following code attempts to detect a cycle in a directed graph but does not work correctly. What is the main error?

void dfs(int node, int visited[], int graph[][3]) {
    visited[node] = 1;
    for (int i = 0; i < 3; i++) {
        int adj = graph[node][i];
        if (adj == -1) continue;
        if (!visited[adj]) dfs(adj, visited, graph);
        else printf("Cycle detected\n");
    }
}

int main() {
    int graph[3][3] = {{1, -1, -1}, {2, -1, -1}, {0, -1, -1}};
    int visited[3] = {0};
    dfs(0, visited, graph);
    return 0;
}

medium

A. Graph adjacency matrix is incorrect

B. Visited array is not initialized

C. Missing recursion stack to track nodes in current path

D. DFS function missing return type

Solution

1. Step 1: Understand cycle detection logic

   Cycle detection in directed graph needs to track nodes in current recursion path using a recursion stack.

2. Step 2: Identify missing recursion stack

   This code only uses visited array, so it cannot distinguish back edges causing cycles from cross edges.

3. Final Answer:

   Missing recursion stack to track nodes in current path -> Option C

4. Quick Check:

   Recursion stack needed for correct cycle detection [OK]

Hint: Use recursion stack to detect back edges in DFS [OK]

Common Mistakes:

• Assuming visited array alone detects cycles
• Ignoring need to track current DFS path
• Confusing undirected and directed cycle detection

5. You have a directed graph represented as adjacency lists:

0: [1]
1: [2]
2: [3, 4]
3: [1]
4: []

Which nodes are part of a cycle detected by DFS cycle detection algorithm?

hard

A. Nodes 1, 2, 3

B. Nodes 0, 1, 4

C. Nodes 0, 2, 4

D. Nodes 3, 4

Solution

1. Step 1: Trace the graph edges

   Edges: 0->1, 1->2, 2->3 and 2->4, 3->1.

2. Step 2: Identify cycle nodes

   Cycle is 1->2->3->1. Nodes 1, 2, 3 form the cycle.

3. Final Answer:

   Nodes 1, 2, 3 -> Option A

4. Quick Check:

   Cycle nodes = 1, 2, 3 [OK]

Hint: Follow edges to find loops including nodes [OK]

Common Mistakes:

• Including nodes not in cycle like 0 or 4
• Missing node 3 in cycle
• Confusing cycle with path