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 tasks based on their 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 task dependency graph.

🎯 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 directed graph using adjacency list representation

Use DFS to detect cycles in the graph

Maintain visited and recursion stack arrays to track nodes

Print Cycle detected if a cycle exists, otherwise print No cycle detected

💡 Why This Matters

🌍 Real World

Cycle detection is crucial in task scheduling, deadlock detection, and dependency resolution in software and systems.

💼 Career

Understanding cycle detection helps in roles like software developer, system engineer, and data engineer where graph algorithms are applied.

1

Create the directed graph using adjacency list

Create a vector of vectors called graph with size 4 to represent the directed graph. Add edges exactly as follows: from node 0 to 1, from node 1 to 2, from node 2 to 3, and from node 3 to 1.

DSA C++

# Create the graph adjacency list with 4 nodes
// Your code here

Hint

Use vector> graph(4); to create the graph. Use graph[node].push_back(neighbor); to add edges.

2

Add visited and recursion stack vectors

Add two boolean vectors called visited and recStack of size 4, initialized with false. These will track visited nodes and nodes in the current recursion stack.

DSA C++

#include 
#include 

using namespace std;

int main() {
    vector> graph(4);
    graph[0].push_back(1);
    graph[1].push_back(2);
    graph[2].push_back(3);
    graph[3].push_back(1);

    // Create visited and recStack vectors
    // Your code here

    return 0;
}

Hint

Use vector visited(4, false); and vector recStack(4, false); to create these vectors.

3

Implement DFS function to detect cycle

Write a function called bool dfs(int node, vector>& graph, vector& visited, vector& recStack) that returns true if a cycle is detected starting from node. Mark node as visited and add it to recStack. For each neighbor, if it is not visited, recursively call dfs. If neighbor is in recStack, return true. Remove node from recStack before returning false. Then, in main, use a for loop from 0 to 3 to call dfs on unvisited nodes and detect cycle.

DSA C++

#include 
#include 

using namespace std;

// Write dfs function here

int main() {
    vector> graph(4);
    graph[0].push_back(1);
    graph[1].push_back(2);
    graph[2].push_back(3);
    graph[3].push_back(1);

    vector visited(4, false);
    vector recStack(4, false);

    // Use dfs in main to detect cycle
    // Your code here

    return 0;
}

Hint

Use recursion to explore neighbors. Track nodes in recursion stack to find back edges indicating cycles.

4

Print the result of cycle detection

Add a print statement in main to display Cycle detected if cycleFound is true, otherwise print No cycle detected.

DSA C++

#include 
#include 

using namespace std;

bool dfs(int node, vector>& graph, vector& visited, vector& recStack) {
    visited[node] = true;
    recStack[node] = true;

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

    recStack[node] = false;
    return false;
}

int main() {
    vector> graph(4);
    graph[0].push_back(1);
    graph[1].push_back(2);
    graph[2].push_back(3);
    graph[3].push_back(1);

    vector visited(4, false);
    vector recStack(4, false);

    bool cycleFound = false;
    for (int i = 0; i < 4; i++) {
        if (!visited[i]) {
            if (dfs(i, graph, visited, recStack)) {
                cycleFound = true;
                break;
            }
        }
    }

    // Print cycle detection result
    // Your code here

    return 0;
}

Hint

Use if (cycleFound) cout << "Cycle detected" << endl; else cout << "No cycle detected" << endl;

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