Detect Cycle in a Directed Graph (using Kahn's Algorithm)

We previously discussed a DFS-based solution using a recursion stack to detect cycles in a directed graph. Alternatively, we can use Kahn's BFS-based Topological Sort Algorithm to solve the same problem.

The Logic

Kahn's algorithm can only completely order all vertices if the graph is a Directed Acyclic Graph (DAG). If a cycle is present in the graph:

Some vertices in the cycle will have incoming edges that never get removed.
Their in-degree will never reduce to 0.
Consequently, they will never be enqueued or counted in the final topological ordering list.

Thus, we can run Kahn's algorithm and count the total number of visited/processed nodes:

If visitedCount === V (total vertices), the graph has no cycles.
If visitedCount !== V, the graph contains at least one cycle.

Visual Example

Consider this directed graph containing cycles:

In this graph:

There is a cycle: 2 -> 4 -> 2.
Initial in-degrees: 0: 0, 1: 1, 2: 2 (edges from 1 and 4), 3: 1, 4: 1.
Step 1: Enqueue 0 (in-degree is 0).
Step 2: Pop 0. Decrement neighbors. In-degree of 1 becomes 0 $\rightarrow$ Enqueue 1. (Count = 1).
Step 3: Pop 1. Decrement neighbors. In-degree of 2 becomes 1 $\rightarrow$ Not enqueued. (Count = 2).
Queue is now empty! The loop exits.
Result: Count = 2, which is less than the total vertices 5. Therefore, the graph contains a cycle.

JavaScript Code Implementation

class Graph {
    constructor() {
        this.list = {};
    }
 
    addVertex(vertex) {
        if (!this.list[vertex]) this.list[vertex] = [];
    }
 
    addEdge(v1, v2) {
        this.addVertex(v1);
        this.addVertex(v2);
        this.list[v1].push(v2); // Directed edge v1 -> v2
    }
 
    // BFS-based Cycle Detection
    isCyclic() {
        const in_degree = {};
        const queue = [];
        let visitedCount = 0;
 
        // Initialize in-degrees
        Object.keys(this.list).forEach(vertex => {
            in_degree[vertex] = 0;
        });
 
        // Compute in-degrees of all vertices
        Object.keys(this.list).forEach(u => {
            const neighbors = this.list[u] || [];
            neighbors.forEach(v => {
                in_degree[v] = (in_degree[v] || 0) + 1;
            });
        });
 
        // Enqueue all vertices with in-degree 0
        Object.keys(this.list).forEach(vertex => {
            if (in_degree[vertex] === 0) {
                queue.push(vertex);
            }
        });
 
        // Process queue
        while (queue.length > 0) {
            const u = queue.shift();
            visitedCount++;
 
            const neighbors = this.list[u] || [];
            for (let v of neighbors) {
                in_degree[v]--;
                // Enqueue if all dependencies are resolved
                if (in_degree[v] === 0) {
                    queue.push(v);
                }
            }
        }
 
        const totalVertices = Object.keys(this.list).length;
 
        // If count of visited nodes is not equal to total vertices, there is a cycle
        return visitedCount !== totalVertices;
    }
}
 
// Driver code matching the cycle example
const g = new Graph();
g.addEdge("0", "1");
g.addEdge("1", "2");
g.addEdge("2", "3");
g.addEdge("2", "4");
g.addEdge("4", "2");
 
console.log("Graph contains cycle:", g.isCyclic()); // Output: true

Complexity Analysis

Time Complexity: $O(V + E)$
- Standard linear scan of all edges and vertices.
Space Complexity: $O(V)$
- Storing the in_degree map and the BFS queue requires linear space.

Topological Sort (Kahn's Algorithm)Prim's MST Algorithm