Kahn’s Algorithm is a BFS-based algorithm for topological sorting of a Directed Acyclic Graph (DAG). It is widely used in solving problems that involve task scheduling, dependency resolution, and cycle detection in directed graphs. This framework provides a step-by-step guide to mastering Kahn’s Algorithm.
1. Understanding the Concept of Topological Sorting
Topological sorting is:
• A linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u -> v , vertex u appears before v in the ordering.
• A representation of the dependencies between tasks, where a task v cannot start until task u is completed.
Example
Consider this graph:
• Vertices: 1, 2, 3
• Edges: 1 -> 2, 2 -> 3
The graph represents the dependencies:
• Task 2 depends on 1 being completed.
• Task 3 depends on 2 being completed.
A valid topological order for this graph would be:
[1, 2, 3]
Why DAGs (Directed Acyclic Graphs)?
Topological sorting is only possible for DAGs, which are directed graphs without cycles. This restriction exists because:
1. A cycle introduces a circular dependency:
• For example, if A -> B -> C -> A , there’s no valid way to order A, B, C since each depends on another.
2. In a DAG:
• There’s always at least one vertex with no incoming edges (in-degree = 0). This vertex serves as a natural starting point for the sorting.
2. Understand Kahn’s Algorithm
Kahn’s Algorithm relies on understanding four key components: the in-degree array, queue, topological order list, and cycle detection. Mastering these components will help you solve a wide range of problems, from task scheduling to dependency resolution. Let’s dive into each component in detail.
import java.util.*;
public class TopologicalSort {
public List<Integer> topologicalSort(int numVertices, List<List<Integer>> adjList) {
int[] inDegree = new int[numVertices];
for (int i = 0; i < numVertices; i++) {
for (int neighbor : adjList.get(i)) {
inDegree[neighbor]++;
}
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numVertices; i++) {
if (inDegree[i] == 0) queue.offer(i);
}
List<Integer> topologicalOrder = new ArrayList<>();
while (!queue.isEmpty()) {
int current = queue.poll();
topologicalOrder.add(current);
for (int neighbor : adjList.get(current)) {
inDegree[neighbor]--;
if (inDegree[neighbor] == 0) queue.offer(neighbor);
}
}
if (topologicalOrder.size() != numVertices) {
throw new IllegalArgumentException("Graph contains a cycle");
}
return topologicalOrder;
}
}1. In-degree Array
The in-degree array keeps track of the number of incoming edges (dependencies) for each vertex in the graph.
What is In-degree?
• The in-degree of a vertex v is the number of edges pointing to v .
• For example, in the graph:
1 -> 2, 2 -> 3, 1 -> 3
• Vertex 1 : in-degree = 0 (no edges point to 1 ).
• Vertex 2 : in-degree = 1 (edge 1 -> 2 ).
• Vertex 3 : in-degree = 2 (edges 2 -> 3 and 1 -> 3 ).
int[] inDegree = new int[numVertices];
for (int i = 0; i < numVertices; i++) {
for (int neighbor : adjList.get(i)) {
inDegree[neighbor]++;
}
}2. Queue
The queue is used to manage vertices with an in-degree of 0, meaning they have no dependencies and can be processed immediately.
Key Properties:
• The queue operates in FIFO (First In, First Out) order.
• As vertices are processed, their neighbors’ in-degrees are reduced, and newly eligible vertices (in-degree = 0) are added to the queue.
Why is the Queue Important?
• It ensures that vertices are processed in the correct order, respecting their dependencies.
• Vertices with no incoming edges are the starting points for the sorting.
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numVertices; i++) {
if (inDegree[i] == 0) queue.offer(i);
}3. Topological Order List
The topological order list stores the final result of the topological sorting. It’s a linear ordering of the vertices that satisfies all dependencies.
How is it Constructed?
• As vertices are removed from the queue, they are added to the topological order list.
• The neighbors of each processed vertex have their in-degrees reduced. If a neighbor’s in-degree becomes 0, it’s added to the queue.
List<Integer> topologicalOrder = new ArrayList<>();
while (!queue.isEmpty()) {
int current = queue.poll();
topologicalOrder.add(current);
for (int neighbor : adjList.get(current)) {
inDegree[neighbor]--;
if (inDegree[neighbor] == 0) queue.offer(neighbor);
}
}4. Cycle Detection
A key feature of Kahn’s Algorithm is its ability to detect cycles in a graph. Cycles are problematic because they prevent a valid topological order from existing.
How Cycle Detection Works:
• If the graph contains a cycle, not all vertices can be processed.
• After processing all vertices in the queue, the size of the topological order list should equal the total number of vertices in the graph.
• If the sizes don’t match, the graph contains a cycle.
if (topologicalOrder.size() != numVertices) {
throw new IllegalArgumentException("Graph contains a cycle");
}Summary
Understanding the key components of Kahn’s Algorithm is crucial for mastering topological sorting:
1. In-degree Array: Tracks the number of dependencies for each vertex.
2. Queue: Manages vertices with no dependencies, ensuring the correct processing order.
3. Topological Order List: Stores the final sorted order of vertices.
4. Cycle Detection: Ensures the graph is a DAG by verifying that all vertices are processed.
By breaking the problem into these components, Kahn’s Algorithm provides an elegant and efficient way to solve dependency-related challenges in graphs. Whether you’re solving task scheduling problems or resolving package dependencies, mastering these components is a must!
