Introduction
Suppose you are getting ready for work and there are six pieces of clothing you need to put on; how can you put them on so that you will not have to take them off after wearing them. You do not want to wear a tie before your shirt. A tie is supposed to be on the shirt. Wearing the clothing needs to be in order. This analogy is an example of topological sorting.Let us know about the basics of Kahn’s algorithm topological sorting and its application in this article.
Topological sorting is a straight ordering of the node (or vertices) of a directed graph in a way that for each directed edge from node A to node B, A comes before B in the order. The type of graphs with topological sorting is called Directed Acyclic Graphs (DAG). A DIG is a finite directed graph without directed circles.
Kahn’s algorithm topological sorting
Kahn’s algorithm is an easy topological sort algorithm used, especially in computer sciences, to find an ordering in O(V+E) time. Kahn’s algorithm is one of three types of topological sorting. Kahn outlined it in 1962, and it works by selecting nodes in the same order as the ultimate topological sort.
Basic of Kahn’s algorithm topological sorting
Before going into more details about the Kahn’s Algorithm Topological Sorting, there are some terms we will have to revise:
- Vertex: they are also called nodes.
- Edge: a connection between two subsequent nodes.
- Path: series of nodes to go through one node to another.
- Cycle: a way where a beginning and an ending node are the same.
- Degree: this refers to the total edges connected to a particular node.
- In-degree: this is the entire incoming edge for a specific node.
- Out-degree: this is the whole outgoing edge for a particular node.
The foundation for Kahn’s algorithm
The foundation of Kahn’s algorithm follows the claim below:
There is at least one node with the in-degree zero and one node with the out-degree zero in a directed acyclic graph.
To prove this claim for any directed acyclic graph. We would have to consider a path T that represents the path in Q. From the assertion, we know that:
- T is directed and acyclic; that is to say, it has a starting and end point.
- The longest path is T if and only if the in-degree of the beginning node is zero and the end node is zero.
- The most extended path, T, will always exist since DAG has only a finite course.
Outline of Kahn’s algorithm
Kahn’s algorithm records the number of in-coming edges entering every node. It constantly does the following:
- It finds the node with no in-degree (nodes that do not depend on any other node).
- Keep the nodes with no in-degree in a queue and remove them from the actual graph.
- Removes the edges that started from the nodes stored in the previous step.
The process will continue until no node with an in-degree is present in the graph, and this will only occur at the point when the topological sorting completes. As a result, the algorithm scans the result if the sorting contains the same number of nodes. If the number of nodes matches, Kahn’s Algorithm does not encounter any cycle, and therefore the sorted order will be printed. If the number of nodes does not match, the algorithm meets a cycle, and consequently, the sorting is impossible.
How Kahn’s algorithm topological sorting?
As already mentioned, we repeatedly remove nodes with no directed edges facing them. These nodes with no directed edges pointing to them have directed edges leaving them (that is, it begins from them and points to another node).
Remove every outgoing node that their source nodes get from being deleted. Hence reducing the in-degree of their final nodes and then making new nodes that will not depend on any other node.
The operation will continue until all nodes do not exist, and we obtain a topological ordering of the directed acyclic graph.
Example of Kahn algorithm topological sorting
Using Kahn’s Algorithm Topological Sorting from the above, since node one and node two do not have any in-degree (arrow pointing to them), we delete them first. After deleting nodes one and 2, one would observe that nodes 4 and 5 will have no in-degree so that one can delete them too. Then we delete node three before node 6. Therefore, from the graph, the following topological ordering is possible:
- 124536
- 125436
- 214536
- 215436
Application of Kahn’s algorithm topological sorting
You can use Kahn’s algorithm to schedule a series of tasks based on their dependencies. Nodes represent these tasks, and there is also an edge from node u to v if node u must occur before task v can begin.
How to find the In-degree of each node?
There are two possible ways of finding the in-degree of every node:
- Collect an in-degree ordering that will keep a record of the node’s transverse arrangement and then increase the counter of the terminus vertex by 1. Time complexity is 0(V+E).
- Transverse the list of each vertex and then increase the in-degree of every node joined to it by 1. Time complexity is 0(V+E).
You can accomplish Kahn’s algorithm easily using computer programming languages like C++, Java, Python3 and JavaScript. It uses the second method to find the in-degrees.
Complexity Analysis
- Time Complexity: 0(V+E).
One will carry out the outer loop V times, and the inner one will perform E times.
- Auxiliary Space: 0(V)
The queue has to keep every node of the graph. Therefore, the required space is 0(V).
Conclusion
Kahn algorithm is used in computer sciences to find nodes in the same order as the topological sort. A topological sorting will be impossible if a graph has at least one cycle. A new diagram occurs depending on the order in which the vertices delete.
Frequent Questions Asked
- Is Kahn’s algorithm a BFS?
Yes. The Kahn algorithm is a BFS.
- Does DAG have topological ordering?
Every DAG must have at least one topological ordering.
- Can topological sorting be done using BFS?
Yes, you can do topological sorting using BSF.
