Cycle Detection in Directed Graph (DFS)

Cycle Detection in Directed Graph using DFS

Cycle detection in a directed graph is an important problem in computer science, particularly in dependency resolution, scheduling, and detecting deadlocks. This blog explains how to detect a cycle in a directed graph using Depth First Search (DFS) with the help of two auxiliary vectors: visited and pathVis. We'll also provide a clear implementation in C++.

---

Approach

1. Graph Representation: A directed graph is represented as an adjacency list.

2. Visited Vectors:

   • visited: Keeps track of whether a node has been visited in any DFS traversal.

   • pathVis: Keeps track of whether a node is part of the current DFS recursion stack.

3. Cycle Detection Logic:

   • If a node is visited and is part of the current recursion stack (pathVis[node] is true), a cycle is detected.

   • After exploring all paths from a node, it is removed from the recursion stack by setting pathVis[node] to false.

4. DFS Function:

   • Traverse all neighbors of the current node.

   • If a neighbor is not visited, recursively call DFS for that neighbor.

   • If a neighbor is visited and part of the current recursion stack, a cycle is present.

5. Iterate for All Nodes:

   • Since the graph may be disconnected, start DFS from each unvisited node.

---

Pseudo Code

Here is a pseudo code to make the approach easier for beginners:

function hasCycle(graph, V):
    visited = [false] * V
    pathVis = [false] * V

    for i from 0 to V-1:
        if not visited[i]:
            if dfs(i, graph, visited, pathVis):
                return true
    return false

function dfs(node, graph, visited, pathVis):
    visited[node] = true
    pathVis[node] = true

    for neighbor in graph[node]:
        if not visited[neighbor]:
            if dfs(neighbor, graph, visited, pathVis):
                return true
        else if pathVis[neighbor]:
            return true

    pathVis[node] = false
    return false

---

Implementation in C++

Below is the C++ code to detect a cycle in a directed graph using DFS:

bool dfs(int node, vector<int> &visited, vector<int> &pathVis) {
    visited[node] = 1; // Mark node as visited
    pathVis[node] = 1; // Mark node in the current path

    // Traverse all neighbors
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            // If the neighbor is not visited, recursively call DFS
            if (dfs(neighbor, visited, pathVis)) {
                return true; // Cycle detected
            }
        } else if (pathVis[neighbor]) {
            // If the neighbor is visited and in the current path, cycle detected
            return true;
        }
    }

    pathVis[node] = 0; // Remove node from the current path
    return false;
}

bool hasCycle() {
    vector<int> visited(V, 0); // Initialize visited vector
    vector<int> pathVis(V, 0); // Initialize pathVis vector

    for (int i = 0; i < V; ++i) {
        if (!visited[i]) {
            // Start DFS from each unvisited node
            if (dfs(i, visited, pathVis)) {
                return true; // Cycle detected
            }
        }
    }
    return false; // No cycle detected
}

---

Explanation of Code

1. Graph Initialization:

   • The constructor initializes the graph with a given number of vertices (V).

   • The adjacency list (adj) is resized to accommodate V vertices.

2. Adding Edges:

   • addEdge adds a directed edge from vertex u to vertex v.

3. DFS Function:

   • Marks the current node as visited and adds it to the recursion stack (pathVis).

   • Traverses all neighbors of the current node. If a neighbor is unvisited, DFS is called recursively. If a visited neighbor is found in the recursion stack, a cycle is detected.

   • Removes the node from the recursion stack before returning.

4. Cycle Detection:

   • hasCycle iterates through all nodes. For each unvisited node, it initiates a DFS to check for cycles.

5. Output:

   • Prints whether the graph contains a cycle.

---

Time and Space Complexity

• Time Complexity:

  • Each vertex and edge is visited once, so the complexity is O(V + E), where V is the number of vertices and E is the number of edges.

• Space Complexity:

  • The space required for the adjacency list is O(V + E).

  • Additional space for the visited and pathVis vectors is O(V).

  • The recursion stack may use space up to O(V) in the worst case.

  • Overall, the space complexity is O(V + E).

---

Applications

• Detecting deadlocks in operating systems.

• Verifying dependencies in build systems or package managers.

• Identifying loops in workflows or processes.

---