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

Graphs

Contents

ProblemExamplesSolutionAlgorithmCodeTimeSpace

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❯

  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.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#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;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(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 CaseO(V + E)Each node and its edges are processed exactly once while maintaining the in-degree and queue.
Worst CaseO(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.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...