Detect Cycle in a Directed Graph | DSA in C++ - Software Development PDF Download

Introduction

In graph theory, a cycle is a path in a graph that starts and ends at the same vertex. Detecting cycles in a directed graph is an essential problem in computer science and is often encountered in various applications, such as detecting deadlock situations or finding dependencies in a directed acyclic graph (DAG). In this article, we will explore different approaches to detect cycles in a directed graph using Data Structures and Algorithms (DSA) in C++.

Understanding Directed Graphs

Depth-First Search (DFS) Approach

The Depth-First Search algorithm is commonly used to traverse graphs. We can detect cycles in a directed graph by performing a modified DFS traversal and keeping track of visited vertices. If we encounter a visited vertex again during the traversal, it indicates the presence of a cycle.

Code Implementation: DFS Approach

#include <iostream>

#include <vector>

using namespace std;

bool isCyclicDFSUtil(int v, vector<bool>& visited, vector<bool>& recStack, vector<vector<int>>& adj) {

    visited[v] = true;

    recStack[v] = true;

    for (int neighbor : adj[v]) {

        if (!visited[neighbor]) {

            if (isCyclicDFSUtil(neighbor, visited, recStack, adj))

                return true;

        }

        else if (recStack[neighbor])

            return true;

    }

    recStack[v] = false;

    return false;

}

bool isCyclicDFS(int numVertices, vector<vector<int>>& adj) {

    vector<bool> visited(numVertices, false);

    vector<bool> recStack(numVertices, false);

    for (int i = 0; i < numVertices; ++i) {

        if (!visited[i]) {

            if (isCyclicDFSUtil(i, visited, recStack, adj))

                return true;

        }

    }

    return false;

}

int main() {

    int numVertices = 4;

    vector<vector<int>> adj(numVertices);

    // Example 1: Graph with a cycle

    adj[0].push_back(1);

    adj[1].push_back(2);

    adj[2].push_back(0);

    if (isCyclicDFS(numVertices, adj))

        cout << "Cycle detected in Example 1\n";

    else

        cout << "No cycle detected in Example 1\n";

    // Example 2: Graph without a cycle

    adj[2].pop_back();  // Removing the edge to break the cycle

    if (isCyclicDFS(numVertices, adj))

        cout << "Cycle detected in Example 2\n";

    else

        cout << "No cycle detected in Example 2\n";

    return 0;

}

Output:

Cycle detected in Example 1

No cycle detected in Example 2

Explanation:

The 'isCyclicDFSUtil' function performs a recursive DFS traversal. It marks the current vertex as visited and adds it to the recursion stack. It then recursively explores all unvisited neighbors. If an unvisited neighbor is found, it calls itself on that neighbor. If the neighbor is already visited and present in the recursion stack, a cycle is detected. After visiting all neighbors, the current vertex is removed from the recursion stack.
The 'isCyclicDFS' function initializes the visited and recursion stack arrays and calls 'isCyclicDFSUtil' for each unvisited vertex. If any call to 'isCyclicDFSUtil' returns true, it means a cycle is detected in the graph.

Breadth-First Search (BFS) Approach

Another approach to detect cycles in a directed graph is to use the Breadth-First Search algorithm. This approach involves checking for back edges while performing BFS traversal. If a back edge is encountered, it indicates the presence of a cycle.

Code Implementation: BFS Approach

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

bool isCyclicBFS(int numVertices, vector<vector<int>>& adj) {

    vector<int> inDegree(numVertices, 0);

    for (int i = 0; i < numVertices; ++i) {

        for (int neighbor : adj[i])

            inDegree[neighbor]++;

    }

    queue<int> q;

    for (int i = 0; i < numVertices; ++i) {

        if (inDegree[i] == 0)

            q.push(i);

    }

    int count = 0;

    while (!q.empty()) {

        int currVertex = q.front();

        q.pop();

        count++;

        for (int neighbor : adj[currVertex]) {

            if (--inDegree[neighbor] == 0)

                q.push(neighbor);

        }

    }

    return count != numVertices;

}

int main() {

    int numVertices = 4;

    vector<vector<int>> adj(numVertices);

    // Example 1: Graph with a cycle

    adj[0].push_back(1);

    adj[1].push_back(2);

    adj[2].push_back(0);

    if (isCyclicBFS(numVertices, adj))

        cout << "Cycle detected in Example 1\n";

    else

        cout << "No cycle detected in Example 1\n";

    // Example 2: Graph without a cycle

    adj[2].pop_back();  // Removing the edge to break the cycle

    if (isCyclicBFS(numVertices, adj))

        cout << "Cycle detected in Example 2\n";

    else

        cout << "No cycle detected in Example 2\n";

    return 0;

}

Output:

Cycle detected in Example 1

No cycle detected in Example 2

Explanation:

The 'isCyclicBFS' function uses an array 'inDegree' to keep track of the in-degree of each vertex. It initializes the in-degree array by counting the number of incoming edges for each vertex. It then performs a BFS traversal starting from the vertices with an in-degree of 0. During the traversal, it decrements the in-degree of each neighbor and enqueues the neighbor if its in-degree becomes 0. If the count of visited vertices at the end is not equal to the total number of vertices, a cycle is detected.

Complexity Analysis

The time complexity of both the DFS and BFS approaches is O(V + E), where V is the number of vertices and E is the number of edges in the graph. The space complexity is O(V) for both approaches.

Sample Problems and Solutions

Problem 1: Given a directed graph, determine if it contains a cycle.

We can use either the DFS or BFS approach discussed above to detect cycles in the graph.

Problem 2: Given a list of dependencies between tasks represented as a directed graph, check if there is any cyclic dependency.

We can apply the cycle detection algorithm to the directed graph representing the task dependencies to check for cyclic dependencies.

Conclusion

Detecting cycles in a directed graph is an important problem in computer science. In this article, we explored two common approaches, DFS and BFS, to detect cycles in a directed graph using DSA in C++. We provided code examples and explanations for each approach. Understanding these algorithms will help you identify and handle cycles efficiently in your graph-related applications.