Cycle Detection in Directed Graph in DSA C - Execution Trace

Concept Flow - Cycle Detection in Directed Graph

Start at each unvisited node

↓

Mark node as visited and in recursion stack

↓

For each neighbor

↓

If neighbor not visited

→Recurse on neighbor

↓

If neighbor in recursion stack

→Cycle detected

↓

Remove node from recursion stack

↓

Repeat for all nodes

↓

No cycle found if all done

The algorithm visits each node, tracks recursion stack to detect back edges indicating cycles.

Execution Sample

DSA C

bool dfs(int node) {
  visited[node] = true;
  recStack[node] = true;
  for (int neighbor : graph[node]) {
    if (!visited[neighbor] && dfs(neighbor)) return true;
    else if (recStack[neighbor]) return true;
  }
  recStack[node] = false;
  return false;
}

DFS visits nodes marking recursion stack to find cycles in directed graph.

Execution Table

Step	Operation	Current Node	Visited Set	Recursion Stack	Action	Cycle Detected	Visual State
1	Start DFS at node 0	0	[0]	[0]	Mark 0 visited and in recursion stack	No	0(visited,recStack)
2	Visit neighbor 1 of 0	1	[0,1]	[0,1]	Mark 1 visited and in recursion stack	No	0->1(visited,recStack)
3	Visit neighbor 2 of 1	2	[0,1,2]	[0,1,2]	Mark 2 visited and in recursion stack	No	0->1->2(visited,recStack)
4	Visit neighbor 0 of 2	0	[0,1,2]	[0,1,2]	0 is in recursion stack -> cycle detected	Yes	Cycle found at 0 in 0->1->2
5	Backtrack from 2	2	[0,1,2]	[0,1]	Remove 2 from recursion stack	Yes	0->1(visited,recStack)
6	Backtrack from 1	1	[0,1,2]	[0]	Remove 1 from recursion stack	Yes	0(visited,recStack)
7	Backtrack from 0	0	[0,1,2]	[]	Remove 0 from recursion stack	Yes	0,1,2 visited
8	Check node 3 (unvisited)	3	[0,1,2,3]	[3]	Mark 3 visited and in recursion stack	Yes	3(visited,recStack)
9	Visit neighbor 4 of 3	4	[0,1,2,3,4]	[3,4]	Mark 4 visited and in recursion stack	Yes	3->4(visited,recStack)
10	No neighbors for 4	4	[0,1,2,3,4]	[3,4]	Remove 4 from recursion stack	Yes	3(visited,recStack)
11	Backtrack from 3	3	[0,1,2,3,4]	[]	Remove 3 from recursion stack	Yes	All nodes visited
12	All nodes checked	-	[0,1,2,3,4]	[]	No cycle found in remaining nodes	Yes	Cycle detected in graph
13	End	-	[0,1,2,3,4]	[]	DFS complete	Yes	Final state

💡 Cycle detected at step 4 when node 0 is found in recursion stack

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 7	After Step 11	Final
visited	[]	[0]	[0,1]	[0,1,2]	[0,1,2]	[0,1,2]	[0,1,2,3,4]	[0,1,2,3,4]
recStack	[]	[0]	[0,1]	[0,1,2]	[0,1,2]	[]	[]	[]

Key Moments - 3 Insights

Why do we check if a neighbor is in the recursion stack to detect a cycle?

Because if a neighbor is in the recursion stack, it means we have a back edge to an ancestor node in the current DFS path, indicating a cycle. See step 4 in execution_table where node 0 is in recStack.

Why do we remove nodes from the recursion stack after visiting all neighbors?

Removing nodes from recursion stack means we finished exploring that path. It prevents false cycle detection from nodes already fully processed. See steps 5-7 where nodes are removed from recStack.

What happens if the graph has disconnected parts?

The algorithm starts DFS from each unvisited node to cover all parts. See steps 8-11 where nodes 3 and 4 are visited after the first cycle detection.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, why is a cycle detected?

A Because node 0 is in the recursion stack

B Because node 2 is not visited

C Because node 1 has no neighbors

D Because recursion stack is empty

💡 Hint

Check the 'Cycle Detected' and 'Recursion Stack' columns at step 4 in execution_table

At which step does the recursion stack become empty after visiting node 0 and its neighbors?

A Step 4

B Step 7

C Step 3

D Step 11

💡 Hint

Look at the 'recStack' variable in variable_tracker after step 7

If node 2 had no edge back to node 0, how would the cycle detection change?

A Cycle would be detected earlier

B No cycle would be detected at step 4

C Recursion stack would never be empty

D Visited set would be empty

💡 Hint

Refer to step 4 in execution_table where cycle is detected due to edge from 2 to 0

Concept Snapshot

Cycle Detection in Directed Graph using DFS:
- Visit each node, mark visited and recursion stack
- For each neighbor:
  - If not visited, recurse
  - If in recursion stack, cycle found
- Remove node from recursion stack after all neighbors
- Repeat for all nodes to cover disconnected parts

Full Transcript

This visualization shows how cycle detection in a directed graph works using depth-first search (DFS). We start DFS from each unvisited node, marking nodes as visited and adding them to a recursion stack to track the current path. When visiting neighbors, if a neighbor is not visited, we recurse into it. If a neighbor is already in the recursion stack, it means we found a back edge, indicating a cycle. After exploring all neighbors, we remove the node from the recursion stack. The execution table traces each step, showing the visited set, recursion stack, and when cycles are detected. The variable tracker shows how visited and recursion stack change over time. Key moments clarify why recursion stack is used and how disconnected graph parts are handled. The visual quiz tests understanding of cycle detection steps and conditions.

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