Why Cycle Detection in Directed Graph in DSA C?

The Big Idea

What if a hidden loop in your tasks silently stops everything from moving forward?

The Scenario

Imagine you are managing tasks where some tasks depend on others to be done first. You try to check manually if there is a loop in these dependencies by looking at each task and its requirements.

The Problem

Manually checking for loops in task dependencies is slow and confusing. You can easily miss a hidden cycle, causing tasks to wait forever. This leads to mistakes and delays.

The Solution

Cycle detection in directed graphs automatically finds if there is a loop in dependencies. It uses a smart way to track visited tasks and detect cycles quickly, saving time and avoiding errors.

Before vs After

✗ Before

for each task:
  check all dependencies manually
  if a dependency points back to the task:
    report cycle

✓ After

bool detectCycle(int node) {
  mark node as visiting;
  for each neighbor:
    if neighbor is visiting return true;
    if neighbor not visited and detectCycle(neighbor) return true;
  mark node as visited;
  return false;
}

What It Enables

This lets you automatically find loops in complex task flows or data dependencies, ensuring smooth and correct processing.

Real Life Example

In software build systems, cycle detection prevents infinite loops in module dependencies, so the build process completes successfully.

Key Takeaways

Manual cycle checks are slow and error-prone.

Cycle detection uses visiting states to find loops efficiently.

It helps manage dependencies safely in many real-world systems.

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