Overview:
Kahn’s algorithm is a method used to find a topological order of a directed acyclic graph (DAG). A topological order is a linear arrangement of the vertices such that for every directed edge (u, v), vertex u comes before v. This is a fundamental algorithm in computer science, particularly useful in scenarios like scheduling tasks, resolving dependencies, and compiling code.
Applications:
- Task Scheduling: Ensures tasks are performed in an order that respects dependencies.
- Build Systems: Determines the sequence of compiling files with dependency constraints.
- Course Prerequisites: Helps identify a valid order to complete courses with prerequisites.
The Kahn’s Algorithm in Simple Terms
Continuously find nodes that has no incoming edges and add them to an array for instance, removing them from the graph. The resulting array will be a valid topological order.
Steps in Kahn’s Algorithm:
-
Calculate In-degrees:
- Compute the in-degree (number of incoming edges) for each vertex in the graph. Vertices with an in-degree of
0have no dependencies and can be processed immediately.
- Compute the in-degree (number of incoming edges) for each vertex in the graph. Vertices with an in-degree of
-
Initialize a Queue:
- Create a queue and enqueue all vertices with an in-degree of
0.
- Create a queue and enqueue all vertices with an in-degree of
-
Process Vertices:
- While the queue is not empty:
- Dequeue a vertex
vand add it to the topological order. - For each neighbor of
v, decrement its in-degree by1. - If a neighbor’s in-degree becomes
0, enqueue it.
- Dequeue a vertex
- While the queue is not empty:
-
Check for Cycles:
- After processing all vertices, if the topological order includes all vertices in the graph, the graph is a valid DAG.
- If some vertices remain unprocessed (in-degree not reduced to
0), the graph contains cycles and a topological order is not possible.
Key Characteristics:
- Time Complexity: O(V+E)O(V + E), where VV is the number of vertices and EE is the number of edges.
- Space Complexity: O(V)O(V) for storing in-degrees and the queue.
Example:
For a graph with vertices and edges representing task dependencies:
- Identify tasks without prerequisites (in-degree
0) and process them first. - Remove these tasks and their outgoing edges from the graph, updating the in-degrees of the dependent tasks.
- Repeat until all tasks are processed or a cycle is detected.
Kahn’s algorithm provides an efficient and straightforward approach to solving topological ordering problems, making it a core technique in graph theory and algorithm design.