Cycle Detection in Directed Graph Using BFS (Kahn’s Algorithm)

Problem Statement❯

Cycle detection in a directed graph is a crucial problem in graph theory, especially for applications like scheduling, dependency resolution, and compiler design. A cycle exists when a node points back to itself through a path of directed edges.

This implementation uses Kahn’s Algorithm, which is a BFS-based approach relying on in-degree tracking of nodes.

If the graph can be topologically sorted (i.e., every node is visited exactly once), it does not contain a cycle. Otherwise, a cycle exists.

Examples❯

Graph (Adjacency List)	Cycle Detected	Description
{ 0: [1], 1: [2], 2: [3], 3: [] }	No	Linear graph with no back edges
{ 0: [1], 1: [2], 2: [0] }	Yes	Cycle exists: 0 → 1 → 2 → 0
{ 0: [1], 1: [2], 2: [], 3: [1] }	No	Disconnected graph with no cycle
{ 0: [1], 1: [2], 2: [3], 3: [1] }	Yes	Cycle exists: 1 → 2 → 3 → 1
{}	No	Empty graph with no nodes or edges

Solution❯

Understanding the Problem

We are given a directed graph, where each edge has a direction from one node to another. Our goal is to check if this graph contains a cycle.

A cycle in a directed graph means that there exists a path where you can start at a node and follow the directed edges to eventually return back to the same node. For example, if there are edges 0 → 1 → 2 → 0, this forms a cycle.

To solve this problem, we will use Kahn’s Algorithm. This algorithm is designed for topological sorting using Breadth-First Search (BFS) and can help us identify cycles.

Step-by-Step Solution with Example

Step 1: Calculate In-Degrees

We start by calculating the in-degree of each node, which is the number of edges coming into that node. If a node has an in-degree of 0, it means nothing depends on it and it can be processed first.

Step 2: Initialize the Queue

We create a queue and add all nodes with in-degree 0 to it. These are the starting points for our BFS traversal.

Step 3: Process Nodes

We repeatedly remove a node from the queue, increment a counter visitedCount, and decrease the in-degree of its neighbors. If any neighbor’s in-degree becomes 0, we add it to the queue.

Step 4: Final Check

After processing, we compare visitedCount with the total number of nodes. If all nodes were visited, there’s no cycle. If some nodes couldn’t be visited due to remaining in-degrees, a cycle exists.

Step 5: Let’s Take an Example

Consider a graph with edges: 0 → 1, 1 → 2, 2 → 0.

Initial in-degrees: 0:1, 1:1, 2:1
No node has in-degree 0, so the queue is empty from the start.
visitedCount remains 0 → Not all nodes processed → A cycle exists.

Step 6: Try Another Example

Now consider edges: 0 → 1, 1 → 2.

Initial in-degrees: 0:0, 1:1, 2:1
Queue starts with node 0.
Process 0 → reduces in-degree of 1 → 1 added to queue.
Process 1 → reduces in-degree of 2 → 2 added to queue.
Process 2 → All nodes are processed → visitedCount = 3 → No cycle.

Edge Cases

Empty Graph: No nodes or edges — trivially has no cycles.
Single Node, No Edges: One node alone has no cycle.
Self-Loop: A node with an edge to itself (e.g., 1 → 1) — is a cycle.
Disconnected Graph: Each component must be checked. Kahn’s algorithm handles this automatically since we process all nodes with 0 in-degree.

Finally

Kahn’s Algorithm is an efficient and intuitive way to detect cycles in a directed graph. It works by trying to construct a topological order, and if that’s not possible due to remaining nodes with non-zero in-degree, a cycle is present.

This approach is beginner-friendly because it builds on the simple idea of removing dependencies layer by layer, and it naturally reveals cycles through the presence of unresolved dependencies.

Algorithm Steps❯

Initialize an inDegree map for all nodes with value 0.
Loop through the graph to compute in-degrees of all nodes.
Create a queue and enqueue all nodes with in-degree 0.
Initialize a visitedCount to 0.
While the queue is not empty:

Dequeue a node.
Increment visitedCount.
For each neighbor:
- Decrement their in-degree by 1.
- If in-degree becomes 0, enqueue the neighbor.

After traversal, if visitedCount is less than total nodes, return true (cycle exists); else false.

Code

JavaScript

function hasCycle(graph) {
  const inDegree = {};
  const queue = [];
  const totalNodes = Object.keys(graph).length;
  let visitedCount = 0;

  // Initialize in-degrees
  for (const node in graph) {
    inDegree[node] = 0;
  }
  for (const node in graph) {
    for (const neighbor of graph[node]) {
      inDegree[neighbor] = (inDegree[neighbor] || 0) + 1;
    }
  }

  // Enqueue nodes with in-degree 0
  for (const node in inDegree) {
    if (inDegree[node] === 0) queue.push(node);
  }

  while (queue.length > 0) {
    const current = queue.shift();
    visitedCount++;
    for (const neighbor of graph[current] || []) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  return visitedCount !== totalNodes;
}

const graph1 = { 0: [1], 1: [2], 2: [0] };
const graph2 = { 0: [1], 1: [2], 2: [] };

console.log("Cycle in graph1:", hasCycle(graph1)); // true
console.log("Cycle in graph2:", hasCycle(graph2)); // false

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(V + E)	Even in the best case, we must visit each node and each edge at least once to calculate in-degrees and simulate the process.
Average Case	O(V + E)	Each node and its edges are processed exactly once while maintaining the in-degree and queue.
Worst Case	O(V + E)	The algorithm still processes every node and edge regardless of the presence or absence of cycles.

Space Complexity❯

O(V)

Explanation: We use additional space for the in-degree map, queue, and visited counter—all of which depend on the number of nodes.

⬅ Previous TopicTopological Sort using Kahn's Algorithm

Next Topic ⮕Course Schedule - Task Ordering with Prerequisites

Comments

Loading comments...