Your goal is to find any Topological Sorted order of a directed accyclic graph with V vertices and E edges.
Topological, Every directed edge u -> v has a linear ordering of vertices whereby vertex u occurs before v in the ordering.
Like this:
Input: V=6 , E = {{2,3}, {3,1}, {4,0}, {4,1}, {5,0}, {5,2}}
Output: 4 5 2 0 3 1
Explanation: In the above output, each dependent vertex is printed after the vertices it depends upon.
Input: V=5 , E={{0,1}, {1,2}, {3,2}, {3,4}}
0 3 4 1 2.
Every dependent vertex in the output above prints following the vertices it depends on.
Kahn’s Algorithm for Topological Sorting is a technique for linear ordering the vertices of a directed graph such that A occurs before B in the sequence for every directed edge from vertex A to vertex B. The method searches frequently for vertices devoid of incoming edges, removes them from the graph, and updates the arriving edges of the surviving vertices. This process keeps on till every vertex has
arranged.
Add to a queue all nodes with in-degree 0.
Although the line isn’t empty:
- Get a node off the queue.
- Reduce the in-degree of the destination node by 1 for every outgoing edge from a removed node.
- Add a destination node to the queue should its in-degree turn zero.
- The graph has a cycle and cannot be topologically sorted if the queue is empty although there are still nodes in the network.
- The topological ordering of the graph is embodied by the queue’s nodes.
How can one ascertain the in-degree of every node?
Initially computing the number of incoming edges to every node will help one determine the in-degree of every node. Go over every edge in the graph one at a time increasing the in-degree of the destination node. This allows you to ascertain every node’s in-degree prior to beginning the sorting procedure.
The study of complexity:
Time Complexity: O(V + E).
The inner for loop will be run E number of times; the outer for loop will run V number of times.
Auxiliary Space: V.
The queue must retain every vertex of the graph. Consequently, the needed space is O(V).
Topological Sort Using Kahn’s Algorithm: Applications
- Course sequencing: Prerequisites for other courses abound in university courses. Kahn’s algorithm allows one to schedule the courses such that the requirements are taken before the ones calling for them.
- Management of software dependencies: Libraries and modules developed on software development usually depend on other libraries and modules. Kahn’s method helps one to install the dependencies in the correct sequence.
- Task scheduling in project management usually depends on one another. Kahn’s approach allows one to arrange the chores such that the dependent ones are completed before those depending on them.
- Data processing pipelines may have dependent results from some of the operations of several processes. Using Kahn’s method will help one to perform the stages in the correct sequence.
- Circuit design: Some components of an electronic circuit could depend on the output of others. Kahn’s approach lets one combine the elements in the proper sequence.