Cycle Detection in Directed Graph using BFS

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.

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.

1. Initialize an inDegree map for all nodes with value 0.
2. Loop through the graph to compute in-degrees of all nodes.
3. Create a queue and enqueue all nodes with in-degree 0.
4. Initialize a visitedCount to 0.
5. While the queue is not empty:
1. Dequeue a node.
2. Increment visitedCount.
3. For each neighbor:
   • Decrement their in-degree by 1.
   • If in-degree becomes 0, enqueue the neighbor.
6. After traversal, if visitedCount is less than total nodes, return true (cycle exists); else false.

#include <stdio.h>
#include <stdlib.h>
#define MAX 100

int inDegree[MAX] = {0};
int adj[MAX][MAX];
int queue[MAX];
int front = 0, rear = 0;

void enqueue(int x) {
    queue[rear++] = x;
}

int dequeue() {
    return queue[front++];
}

int main() {
    int nodes = 3;
    int edges[3][2] = {{0, 1}, {1, 2}, {2, 0}}; // change this to test different graphs

    for (int i = 0; i < 3; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        adj[u][v] = 1;
        inDegree[v]++;
    }

    for (int i = 0; i < nodes; i++) {
        if (inDegree[i] == 0)
            enqueue(i);
    }

    int visited = 0;
    while (front < rear) {
        int current = dequeue();
        visited++;
        for (int j = 0; j < nodes; j++) {
            if (adj[current][j]) {
                inDegree[j]--;
                if (inDegree[j] == 0)
                    enqueue(j);
            }
        }
    }

    if (visited == nodes)
        printf("No cycle detected.\n");
    else
        printf("Cycle detected.\n");

    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

bool hasCycle(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<int> inDegree(n, 0);
    for (auto& neighbors : graph)
        for (int neighbor : neighbors)
            inDegree[neighbor]++;

    queue<int> q;
    for (int i = 0; i < n; i++)
        if (inDegree[i] == 0)
            q.push(i);

    int visited = 0;
    while (!q.empty()) {
        int current = q.front(); q.pop();
        visited++;
        for (int neighbor : graph[current]) {
            if (--inDegree[neighbor] == 0)
                q.push(neighbor);
        }
    }
    return visited != n;
}

int main() {
    vector<vector<int>> graph1 = {{1}, {2}, {0}};
    vector<vector<int>> graph2 = {{1}, {2}, {}};
    cout << "Cycle in graph1: " << hasCycle(graph1) << endl;
    cout << "Cycle in graph2: " << hasCycle(graph2) << endl;
    return 0;
}

from collections import deque

def has_cycle(graph):
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1

    queue = deque([node for node in graph if in_degree[node] == 0])
    visited_count = 0

    while queue:
        current = queue.popleft()
        visited_count += 1
        for neighbor in graph[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return visited_count != len(graph)


graph1 = {0: [1], 1: [2], 2: [0]}
graph2 = {0: [1], 1: [2], 2: []}
print("Cycle in graph1:", has_cycle(graph1))  # True
print("Cycle in graph2:", has_cycle(graph2))  # False

import java.util.*;

public class CycleDetection {
    public static boolean hasCycle(Map<Integer, List<Integer>> graph) {
        Map<Integer, Integer> inDegree = new HashMap<>();
        for (int node : graph.keySet()) inDegree.put(node, 0);
        for (int node : graph.keySet())
            for (int neighbor : graph.get(node))
                inDegree.put(neighbor, inDegree.get(neighbor) + 1);

        Queue<Integer> queue = new LinkedList<>();
        for (int node : inDegree.keySet())
            if (inDegree.get(node) == 0) queue.offer(node);

        int visited = 0;
        while (!queue.isEmpty()) {
            int current = queue.poll();
            visited++;
            for (int neighbor : graph.getOrDefault(current, new ArrayList<>())) {
                inDegree.put(neighbor, inDegree.get(neighbor) - 1);
                if (inDegree.get(neighbor) == 0) queue.offer(neighbor);
            }
        }
        return visited != graph.size();
    }

    public static void main(String[] args) {
        Map<Integer, List<Integer>> graph1 = Map.of(0, List.of(1), 1, List.of(2), 2, List.of(0));
        Map<Integer, List<Integer>> graph2 = Map.of(0, List.of(1), 1, List.of(2), 2, List.of());
        System.out.println("Cycle in graph1: " + hasCycle(graph1));
        System.out.println("Cycle in graph2: " + hasCycle(graph2));
    }
}

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

  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;
    }
  }

  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

package main

import (
	"fmt"
)

func hasCycle(graph map[int][]int) bool {
	inDegree := make(map[int]int)
	totalNodes := len(graph)
	for node := range graph {
		inDegree[node] = 0
	}
	for _, neighbors := range graph {
		for _, neighbor := range neighbors {
			inDegree[neighbor]++
		}
	}
	queue := []int{}
	for node, deg := range inDegree {
		if deg == 0 {
			queue = append(queue, node)
		}
	}
	visited := 0
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		visited++
		for _, neighbor := range graph[node] {
			inDegree[neighbor]--
			if inDegree[neighbor] == 0 {
				queue = append(queue, neighbor)
			}
		}
	}
	return visited != totalNodes
}

func main() {
	graph1 := map[int][]int{0: {1}, 1: {2}, 2: {0}}
	graph2 := map[int][]int{0: {1}, 1: {2}, 2: {}}
	fmt.Println("Cycle in graph1:", hasCycle(graph1))
	fmt.Println("Cycle in graph2:", hasCycle(graph2))
}

use std::collections::{HashMap, VecDeque};

fn has_cycle(graph: &HashMap<usize, Vec<usize>>) -> bool {
    let mut in_degree = HashMap::new();
    for &node in graph.keys() {
        in_degree.insert(node, 0);
    }
    for neighbors in graph.values() {
        for &neighbor in neighbors {
            *in_degree.entry(neighbor).or_insert(0) += 1;
        }
    }
    let mut queue = VecDeque::new();
    for (&node, &deg) in &in_degree {
        if deg == 0 {
            queue.push_back(node);
        }
    }
    let mut visited = 0;
    while let Some(current) = queue.pop_front() {
        visited += 1;
        if let Some(neighbors) = graph.get(&current) {
            for &neighbor in neighbors {
                if let Some(deg) = in_degree.get_mut(&neighbor) {
                    *deg -= 1;
                    if *deg == 0 {
                        queue.push_back(neighbor);
                    }
                }
            }
        }
    }
    visited != graph.len()
}

fn main() {
    let graph1 = HashMap::from([(0, vec![1]), (1, vec![2]), (2, vec![0])]);
    let graph2 = HashMap::from([(0, vec![1]), (1, vec![2]), (2, vec![])]);
    println!("Cycle in graph1: {}", has_cycle(&graph1));
    println!("Cycle in graph2: {}", has_cycle(&graph2));
}

fun hasCycle(graph: Map<Int, List<Int>>): Boolean {
    val inDegree = mutableMapOf<Int, Int>()
    for (node in graph.keys) inDegree[node] = 0
    for (node in graph.keys) {
        for (neighbor in graph[node] ?: emptyList()) {
            inDegree[neighbor] = inDegree.getOrDefault(neighbor, 0) + 1
        }
    }
    val queue = ArrayDeque<Int>()
    for ((node, deg) in inDegree) if (deg == 0) queue.add(node)
    var visited = 0
    while (queue.isNotEmpty()) {
        val current = queue.removeFirst()
        visited++
        for (neighbor in graph[current] ?: emptyList()) {
            inDegree[neighbor] = inDegree[neighbor]!! - 1
            if (inDegree[neighbor] == 0) queue.add(neighbor)
        }
    }
    return visited != graph.size
}

fun main() {
    val graph1 = mapOf(0 to listOf(1), 1 to listOf(2), 2 to listOf(0))
    val graph2 = mapOf(0 to listOf(1), 1 to listOf(2), 2 to listOf())
    println("Cycle in graph1: ${hasCycle(graph1)}")
    println("Cycle in graph2: ${hasCycle(graph2)}")
}

func hasCycle(_ graph: [Int: [Int]]) -> Bool {
    var inDegree = [Int: Int]()
    for node in graph.keys { inDegree[node] = 0 }
    for neighbors in graph.values {
        for neighbor in neighbors {
            inDegree[neighbor, default: 0] += 1
        }
    }
    var queue = [Int]()
    for (node, deg) in inDegree where deg == 0 {
        queue.append(node)
    }
    var visited = 0
    while !queue.isEmpty {
        let current = queue.removeFirst()
        visited += 1
        for neighbor in graph[current] ?? [] {
            inDegree[neighbor]! -= 1
            if inDegree[neighbor] == 0 {
                queue.append(neighbor)
            }
        }
    }
    return visited != graph.count
}

let graph1 = [0: [1], 1: [2], 2: [0]]
let graph2 = [0: [1], 1: [2], 2: []]
print("Cycle in graph1: \(hasCycle(graph1))")
print("Cycle in graph2: \(hasCycle(graph2))")

function hasCycle(graph: Record<number, number[]>): boolean {
  const inDegree: Record<number, number> = {};
  const queue: number[] = [];
  const totalNodes = Object.keys(graph).length;
  let visited = 0;

  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;

  for (const node in inDegree)
    if (inDegree[node] === 0) queue.push(Number(node));

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

  return visited !== totalNodes;
}

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

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

Time complexity

Space complexity

O(V)

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