Cycle Detection in Directed Graph in DSA C++ - Execution Trace

Concept Flow - Cycle Detection in Directed Graph

Start DFS at each unvisited node

↓

Mark node as visited and in recursion stack

↓

For each neighbor

↓

If neighbor not visited

→DFS on neighbor

↓

If neighbor in recursion stack

→Cycle detected

↓

Remove node from recursion stack

↓

Repeat for all nodes

↓

No cycle found

We run DFS from each node, track visited nodes and recursion stack to find back edges indicating cycles.

Execution Sample

DSA C++

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

This code runs DFS to detect cycles by checking if a node is revisited in the current recursion path.

Execution Table

Step	Operation	Current Node	Visited Set	Recursion Stack	Action	Cycle Detected	Graph State
1	Start DFS	0	{}	{}	Mark 0 visited and in stack	No	0 -> [1, 2], 1 -> [2], 2 -> [0, 3], 3 -> []
2	Explore neighbor	0	{0}	{0}	Go to neighbor 1	No	Same
3	Start DFS	1	{0}	{0}	Mark 1 visited and in stack	No	Same
4	Explore neighbor	1	{0,1}	{0,1}	Go to neighbor 2	No	Same
5	Start DFS	2	{0,1}	{0,1}	Mark 2 visited and in stack	No	Same
6	Explore neighbor	2	{0,1,2}	{0,1,2}	Go to neighbor 0	Yes	Same
7	Return	2	{0,1,2}	{0,1,2}	Cycle found, return true	Yes	Same
8	Return	1	{0,1,2}	{0,1,2}	Cycle found, return true	Yes	Same
9	Return	0	{0,1,2}	{0,1,2}	Cycle found, return true	Yes	Same
10	End	-	{0,1,2}	{}	DFS ends due to cycle	Yes	Same

💡 Cycle detected at step 6 when neighbor 0 is found in recursion stack

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 6	Final
visited	{}	{0}	{0,1}	{0,1,2}	{0,1,2}	{0,1,2}
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 instead of just visited?

Because a node being visited means it was explored before, but being in the recursion stack means it's still in the current path, indicating a cycle (see step 6 in execution_table).

What happens when we find a cycle during DFS?

We immediately return true up the call stack to stop further exploration, as shown from steps 6 to 9 in execution_table.

Why do we remove the node from recursion stack after exploring all neighbors?

To mark that the node's path exploration is complete and it is no longer in the current recursion path, preventing false cycle detection (see step 10).

Visual Quiz - 3 Questions

Look at the execution_table, what is the recursion stack after step 3?

A {0,1}

B {0}

C {}

D {1}

💡 Hint

Check the 'Recursion Stack' column at step 3 in execution_table.

At which step does the cycle get detected?

A Step 4

B Step 6

C Step 8

D Step 10

💡 Hint

Look for 'Cycle detected' in the 'Cycle Detected' column in execution_table.

If the graph had no edge from node 2 to node 0, what would happen at step 6?

A Cycle detected anyway

B DFS would stop immediately

C DFS would continue exploring other neighbors

D Recursion stack would be empty

💡 Hint

Step 6 shows cycle detection due to edge 2->0; without it, DFS explores further.

Concept Snapshot

Cycle Detection in Directed Graph using DFS:
- Use two arrays: visited[] and recStack[]
- Start DFS from each unvisited node
- Mark node visited and add to recStack
- For each neighbor:
  - If not visited, DFS on neighbor
  - If in recStack, cycle found
- Remove node from recStack after exploring neighbors
- If any DFS returns true, graph has a cycle

Full Transcript

Cycle detection in a directed graph uses depth-first search (DFS). We keep track of nodes visited and nodes currently in the recursion stack. Starting from each unvisited node, we mark it visited and add it to the recursion stack. We then explore each neighbor. If a neighbor is not visited, we recursively DFS on it. If a neighbor is already in the recursion stack, it means we found a cycle. We return true immediately. After exploring all neighbors, we remove the node from the recursion stack. If no cycles are found after DFS on all nodes, the graph is acyclic. This method detects back edges that form cycles.

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 where you can start from a node and follow edges in their direction to come back to the same node.

2. Step 2: Identify what cycle detection finds

   Cycle detection checks if such a path exists anywhere 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 = find directed loops [OK]

Hint: Cycle means path back to start following edge directions [OK]

Common Mistakes:

• Confusing cycle with shortest path
• Thinking cycle ignores edge directions
• Mixing cycle with node count

2. Which of the following is the correct way to declare a graph adjacency list in C++ for cycle detection?

easy

A. vector graph(100);

B. int graph[100][100];

C. map graph;

D. vector<int> graph[100];

Solution

1. Step 1: Understand adjacency list declaration

   For cycle detection, adjacency list is often a vector of vectors to store edges from each node.

2. Step 2: Check each option

   A: vector graph(100); - standard and flexible vector of vectors for adjacency list. B: adjacency matrix, not list. C: map, valid but less common and heavier for sequential nodes. D: array of vectors, works but fixed size and less modern than vector of vectors.

3. Final Answer:

   vector graph(100); -> Option A

4. Quick Check:

   Use vector of vectors for adjacency list [OK]

Hint: Use vector for flexible adjacency list [OK]

Common Mistakes:

• Using adjacency matrix instead of list
• Confusing map with vector
• Using raw arrays limiting flexibility

3. What will be the output of the following code snippet detecting cycle in a directed graph?

bool dfs(int node, vector& graph, vector<int>& visited, vector<int>& recStack) {
    visited[node] = 1;
    recStack[node] = 1;
    for (int adj : graph[node]) {
        if (!visited[adj] && dfs(adj, graph, visited, recStack))
            return true;
        else if (recStack[adj])
            return true;
    }
    recStack[node] = 0;
    return false;
}

int main() {
    vector graph(3);
    graph[0].push_back(1);
    graph[1].push_back(2);
    graph[2].push_back(0);
    vector<int> visited(3, 0), recStack(3, 0);
    cout << (dfs(0, graph, visited, recStack) ? "Cycle Found" : "No Cycle") << endl;
    return 0;
}

medium

A. Compilation Error

B. Cycle Found

C. No Cycle

D. Runtime Error

Solution

1. Step 1: Analyze graph edges

   Edges: 0->1, 1->2, 2->0 form a cycle (0->1->2->0).

2. Step 2: Understand DFS cycle detection

   DFS uses recursion stack to detect back edges indicating cycle. Here, cycle exists, so dfs returns true.

3. Final Answer:

   Cycle Found -> Option B

4. Quick Check:

   Cycle in 0->1->2->0 detected [OK]

Hint: Check recursion stack for back edges to find cycle [OK]

Common Mistakes:

• Ignoring recursion stack usage
• Assuming no cycle in simple loops
• Confusing visited and recursion stack arrays

4. Find the bug in this cycle detection code snippet for a directed graph:

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

medium

A. Graph should be vector<int> not vector

B. visited array should be int, not bool

C. Missing return statement in else block

D. recStack[node] is never set to true at start

Solution

1. Step 1: Check usage of recStack

   recStack marks nodes in current recursion path. It must be set true when node is entered.

2. Step 2: Identify missing recStack[node] = true

   Code sets recStack[node] = false at end but never sets it true at start, so cycle detection fails.

3. Final Answer:

   recStack[node] is never set to true at start -> Option D

4. Quick Check:

   Set recStack true on node entry [OK]

Hint: Always mark recStack true when entering node [OK]

Common Mistakes:

• Forgetting to set recStack true at start
• Confusing visited and recStack roles
• Wrong data types for visited array

5. Given a directed graph with nodes 0 to 4 and edges: 0->1, 1->2, 2->3, 3->1, 3->4, which nodes are part of a cycle?

hard

A. [0, 1, 2, 3]

B. [2, 3, 4]

C. [1, 2, 3]

D. [0, 4]

Solution

1. Step 1: Analyze edges for cycles

   Edges 1->2, 2->3, 3->1 form a cycle involving nodes 1, 2, 3.

2. Step 2: Identify nodes outside cycle

   Node 0 points to 1 but is not in cycle. Node 4 is only reached from 3 and has no outgoing edges back.

3. Final Answer:

   [1, 2, 3] -> Option C

4. Quick Check:

   Cycle nodes = 1, 2, 3 [OK]

Hint: Cycle nodes form closed loop edges [OK]

Common Mistakes:

• Including nodes only pointing into cycle
• Including nodes with no back edges
• Confusing cycle membership with reachability