Cycle Detection in Directed Graph in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a cycle in a directed graph?

A cycle in a directed graph is a path that starts and ends at the same vertex, following the direction of edges, without repeating any vertex.

beginner

Which data structures are commonly used to detect cycles in a directed graph?

Depth-First Search (DFS) with recursion stack or colors (white, gray, black) is commonly used to detect cycles in directed graphs.

intermediate

Explain the role of the recursion stack in DFS for cycle detection.

The recursion stack keeps track of vertices currently in the path. If during DFS, we visit a vertex already in the recursion stack, it means a cycle exists.

intermediate

What is the difference between visited and recursion stack arrays in cycle detection?

The visited array marks all nodes that have been explored, while the recursion stack marks nodes currently in the active DFS path to detect back edges indicating cycles.

intermediate

Why can't cycle detection in directed graphs be done by just checking visited nodes?

Because revisiting a visited node does not always mean a cycle; it must be in the current DFS path (recursion stack) to confirm a cycle in directed graphs.

What does it mean if a node is found in the recursion stack during DFS?

A A cycle is detected

B The node is fully processed

C The node is unvisited

D The graph is disconnected

Finding a node in the recursion stack means we have a back edge, indicating a cycle.

Which traversal method is typically used for cycle detection in directed graphs?

A Breadth-First Search (BFS)

B Dijkstra's Algorithm

C Depth-First Search (DFS)

D Prim's Algorithm

DFS is used because it can track the recursion stack to detect cycles.

What does the 'visited' array represent in cycle detection?

A Nodes currently in the recursion stack

B Nodes that have been explored at least once

C Nodes that are unreachable

D Nodes with no outgoing edges

The visited array marks nodes that have been explored to avoid repeated work.

If no node is found in the recursion stack during DFS, what can we conclude?

A The graph has no cycles

B The graph is disconnected

C The graph contains a cycle

D The graph is undirected

No node in recursion stack means no back edge, so no cycle.

Which of these is a sign of a cycle in a directed graph during DFS?

A Visiting a node that is not visited

B Visiting a node with no incoming edges

C Visiting a node with no outgoing edges

D Visiting a node that is in recursion stack

Visiting a node in recursion stack means a cycle is detected.

Describe how Depth-First Search (DFS) can be used to detect a cycle in a directed graph.

Think about tracking nodes in the current path.

Explain why simply checking if a node is visited is not enough to detect cycles in directed graphs.

Consider the difference between nodes visited before and nodes in the current path.

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