Topological sorting is a linear ordering carried out on directed acyclic graphs (DAG) in which a node or vertex v is visited only after all its dependent vertices are visited, that is, for every directed edge for vertex v to vertex u, v comes before u in the linear ordering. This is only able to be done if the graph is directed acyclic. Acyclic graphs are graphs having no cycles or closed paths. If the graph consists of vertices and edges, in which each edge is directed from one vertex to another without a closed-loop formation it is called a Directed Acyclic Graph (DAG). Let us know more detail about ‘Kahn’s Algorithm For Topological Sorting’.
Kahn’s Algorithm For Topological Sorting
Suppose a user initiates to view a movie with process P1 holding a resource R1. He then initiates a livestream process P2 which requires the use of resource R2 and then decides to view the same movie on an external screen with process P3 using resource R3. If each process holds its resource, then P3 will be waiting on R1 while P1 is waiting on R2 and P2 is waiting on R3. This highlighted scenario can be represented as a directed graph. Why? A process must be executed successfully before executing the next process. Here’s how the graph cycle will look like:
This results in a graph cycle called a deadlock in operating systems which can be identified using Kahn’s algorithm for topological sorting.
Kahn’s Algorithm for topological sorting
Different and various algorithms have been used to implement topological sorting. Some algorithms are based on Breadth-first search, Depth-first search, and parallel algorithms. Our focus will be on Kahn’s Algorithm. The algorithm was first depicted in 1962, in which vertices are nominated in the same order as the topological sort. The steps involved are:
Step 1: Create a list of vertices array (V) called graph.
Step 2: Create a queue called in-degree (Q).
Step 3: Calculate the in-degree (I) of each of the vertices and the number of Nodes (N) present in the DAG.
Step 4: Initialize the count (C) of visited nodes starting at 0.
Step 5: Select all the vertices with I=0 and add them into a queue (En-queue all vertices with degree 0).
Step 6: Remove a vertex from the queue (De-queue a vertex from the queue) and place it in a Sorted Array (Y).
Step 7: Increase the count (C) of visited nodes by 1.
Step 8: Decrease the in-degree of all the neighbouring vertex of the currently de-queued element by 1.
Step 9: if the in-degree of neighbouring nodes becomes 0, add it to the queue.
Step 10: Repeat step 6 to 9 until the queue is empty.
Step 11: If count C ≠ N then topological sort is not possible.
Step 12: If the queue becomes empty return the sorted array (Y).
Step 13: Print contents of the returned sorted array.
Topological sorting example using Kahn’s Algorithm
For Example, suppose the graph given below is to be sorted using Kahn’s Algorithm:
The in-degree is computed and the “sorted array” is empty
| IN DEGREE | 0 | 1 | 2 | 0 | 2 | 1 |
| VERTICES ARRAY | 1 | 2 | 3 | 4 | 5 | 6 |
| SORTED ARRAY (Y) |
Next, we delete 1 and 4 from the queue and add them to the sorted array. The vertices connected to 1 are 2 and 3 and the vertices connected to 4 are 3 and 5. So their in-degree is reduced by 1.
| IN DEGREE | 0 | 0 | 1 | 0 | 1 | 0 |
| VERTICES ARRAY | 1 | 2 | 3 | 4 | 5 | 6 |
| SORTED ARRAY (Y) | 1 |
| IN DEGREE | 0 | 0 | 1 | 0 | 1 | 0 |
| VERTICES ARRAY | 1 | 2 | 3 | 4 | 5 | 6 |
| SORTED ARRAY (Y) | 1 | 4 |
Next, we delete 2 and 6 from the queue and add them to the sorted array. The vertex connected to 2 is 6 and the vertex connected to 6 is 5. So their in-degree is reduced by 1 if still in the queue.
| IN DEGREE | 0 | 0 | 1 | 0 | 1 | 0 |
| VERTICES ARRAY | 1 | 2 | 3 | 4 | 5 | 6 |
| SORTED ARRAY (Y) | 1 | 4 | 2 |
| IN DEGREE | 0 | 0 | 1 | 0 | 1 | 0 |
| VERTICES ARRAY | 1 | 2 | 3 | 4 | 5 | 6 |
| SORTED ARRAY (Y) | 1 | 4 | 2 | 6 |
Next, we delete 5 from the queue and add them to the sorted array.
| IN DEGREE | 0 | 0 | 1 | 0 | 0 | 0 |
| VERTICES ARRAY | 1 | 2 | 3 | 4 | 5 | 6 |
| SORTED ARRAY (Y) | 1 | 4 | 2 | 6 | 5 |
The remaining vertex is 3 which is not connected to any other vertices. The in-degree is also reduced by 1 and added to the sorted array.
| IN DEGREE | 0 | 0 | 1 | 0 | 0 | 0 |
| VERTICES ARRAY | 1 | 2 | 3 | 4 | 5 | 6 |
| SORTED ARRAY (Y) | 1 | 4 | 2 | 6 | 5 | 3 |
The topological sort using Kahn Algorithm is Y: 1,4,2,6,5,3
Complexity Analysis
Kahn’s algorithms are a complexity of O(V+E) and O(V) for time and space respectively where V is the number of vertices and E is the number of edges. The space complexity essentially caters for the space required by the queue to store all the vertices of the graph.
Uses of Topological sorting
Kahn’s topological sorting like other sorting algorithms can be used for:
- Critical Path Analysis: Critical path analysis is a project management technique which enables to deduce of how long a project will take.
- Course Scheduling: Topological sorting is very helpful in solving course scheduling problems as it caters for course perquisites in any class.
- Operation System Deadlock: A deadlock occurs when a process is waiting for a resource while another process holds the requested resources.
In Conclusion,
Topological Sort is an algorithm which sorts a directed graph by returning an array that consists of nodes where each node appears before all the nodes it points to. It is worthy of note that there can be multiple topological sort for a graph. Kahn’s algorithm is a popularly accepted topological sorting algorithm which entails the continuous finding of nodes with zero indegree and adding them to a sorted array while deleting outgoing edges.
