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.
Comments
Loading comments...