Topological sort of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. PS: Topological sorting is possible only if the graph is a directed acyclic graph.
Two commom approaches for topological sort:
- Kahn's algorithm
- Depth - first search
The code here is an implementation of Kahn's algorithm.
This is computationally simpler compared to DFS approach.
Step 1: Find all the nodes in the graph with in-degree as 0 and add them into a queue Step 2: Remove the nodes from the queue one by one, append it to the sorted_list and simulatneously update the graph(remove the node from the graph, resulting which, in-degree of nodes which had edges directed from the reomved node decreases by one). Step 3: If there are anymore nodes left in the graph, go back to step 1
This method is optimal but modifies the graph. For the algorithm to not modify the original graph, you'll need to maintain a boolean array visited[] - to keep track to the visited nodes and indegree[] to store the in-degree of the graph nodes.
Consider the sample input below:
6
1 2
1 3
2 3
2 4
3 4
3 5
Visualization of the input graph:
Node 1 is the only node with in-degree as 0. Remove it from the graph, and append it to the sorted_list. sorted_list = [1]
Now, Node 2 has an in-degree of 0. Remove it from the graph, and append it to the sorted list. sorted_list = [1,2]
Next, Node 3 has an in-degree of 0. sorted_list = [1,2 3]
Next, Node 4 and Node 5, both have an in-degree of 0. sorted_list = [1,2,3,4,5] Note that: [1,2,3,5,4] is also the right order.
Visualization of the topologically sorted order.
Green node - denotes the starting node.
Red node - denotes the final node.
