Kahn’s Algorithm-Know More

If you are searching for how to sort algorithms then this article is the best guide for you. For the preparation of the technical interview, sorting algorithms are one of the most crucial parts. In sorting algorithms, there is one sort, i.e., topological sorting which has been designed for DAGS (directed acyclic graphs.Using different types of algorithms such as Kahn’s algorithm, depth-first search the topological sorting can be sorted. In this article, you will get to know about Kahn’s algorithm which is also known as Kahn’s topological sort. Kahn’s algorithm helps software engineers to solve complex problems very easily. let us know more about that the Kahn’s Algorithm-Know More.

Some basic points of Kahn’s algorithm

In Kahn’s algorithm, it is stated that DAG G (directed acyclic graph) has one vertex with the in-degree zero and another vertex with the out-degree zero. Now let’s see whether this statement is true or not:

 DAG G (directed acyclic graph) doesn’t contain a cycle. No endless loop is there in DAG G as there is no cycle. In G all parts have a finishing point.If you analyze that the path P represents the path of G, you will come to know that:

 Path P has a beginning and also has an end as it is acyclic and directed. Path p begins from the vertex u source and ends at vertex v source.

Path P exists longer as DAG has finite paths. This shows that DAG has one vertex with zero indegrees and also has one vertex with zero in degrees.

The vertex source u does not have any incoming edge and the vertex source v does not have any outgoing edge as path P has the longest path which is acyclic and finite. 

How does the process of Kahn’s algorithm work?

In this topic, you will get to know how Kahn’s algorithm works. In Kahn’s algorithm, the nodes with zero directed edges are removed. These 0 indegree nodes have outgoing edges which are directed.When the source nodes are deleted, the outgoing edges are removed. As the outgoing edges are removed the indegrees of the nodes are reduced and zeroes are created with more dependencies of zeroes. This process continues to work till the nodes are removed and this process gives a directed acyclic graph i.e., DAG. There are five important steps to understanding the following process: 

First, you have to store the in-degree of every node and you have to keep a watch on how many nodes have come to zero.

Second, you have to take each node with 0 in degrees and then you have to add the nodes to a queue or an enqueue or a stack or a push. 

Third, remove the nodes from a queue or a stack and:

1. Count the visited nodes one by one.
2. From the neighboring nodes reduce the indegree by one.
3. If the indegree of the neighboring node comes to zero by the above process then add the nodes to a queue or a stack.

Fourth, continue to do the third process till you see that the queue or stack is empty.

Fifth, a topological sorting cannot be possible if the visited nodes are not equal to the number of nodes according to the graph. According to the graph, if the nodes are equal to the number of nodes then topological sorting can be done.

Examples of Kahn’s algorithm

You will be able to understand the concept of Kahn’s algorithm, topological sorting by going through some examples:

The examples are as follows:

Edges: {0, 1}, {0, 2}, {1, 3}, {1, 4}, {3,4}, {3,5}

Removal in order: First remove 0, then 1 and 2, then 3, and at the end 4 and 5.

In topological order: 0,1,2,3,4,5

You have to keep in mind that the above topological order is not the exact topological order.

0,1,3,4,5,2 is a valid topological order.

Now, you have to calculate the indegree of every node. The indegree of a node is defined as several edges that point toward the node. 

In the concept of edge every edge such as {Ui, V}, Ui is referred to as the source whereas V is referred to as the destination node. You have to update the indegree value of node V when edging associates with it. For example:

1. 0 node has 0 incoming edges i.e., In= 0
2. 1, 2, 3 nodes and 5 have 1 incoming edge i.e., In= 1
3. 4 nodes have 2 incoming edges i.e., In= 2

There are 5 processes of using Kahn’s algorithm for topological sorting:

• The node zeroes indegree is 0. This node with indegree zero is removed and its outward edges are {0,1} and {0,2}.

• You have to update the indegree nodes of the deleted edges and the edges which are directed, it points towards the destined nodes. The indegree of one and two nodes decreased by one.

• Decrease the 3 and 4 edges and then the indegree of node 4 starts from 2 to 1 and the indegree of node 3 starts from 1 to 0. 

• You have to update the indegrees of the nodes and then the indegrees of 4 and 5 nodes decrease by one and become 0. 

• Various topological sorting can be done in an acyclic graph. The processes are repeated until the nodes are sorted and the outputs are given. A valid topographical is as follows: 

0, 1, 2, 3, 4, 5

What are the uses of Kahn’s algorithm?

The uses of Kahn’s algorithm are as follows:

1. Kahn’s algorithm finds the indegree of all nodes. 
2. Kahn’s algorithm identifies a node.
3. Kahn’s algorithm decreases the indegree for which edges were deleted.
4. Kahn’s algorithm checks that all elements are presented in the sequence of sorted or not.
5. Kahn’s algorithm removes from the graph the outgoing edges of nodes.
6. Kahn’s algorithm repeats the steps from one to four until the nodes become zero.

Conclusion

This article will solve your problems about how to use Kahn’s algorithm for topological sorting. There are many algorithms by which topological sorting can be done and, in this article, Kahn’s algorithm has been discussed.You will get to know about some of the examples of Kahn’s algorithm and how the process of Kahn’s algorithm works and your doubts will be solved also about how Kahn’s algorithm works.

FAQs

What does topological sort use?

Topological sorts use DFS and BFS.

Is the DFS algorithm faster than the BFS algorithm?

Yes, the DFS algorithm is faster than the BFS algorithm.

Is DFS better than BFS?

 Yes, DFS is better than BFS.

Mention the algorithms in which shortest paths can be found.

The algorithms in which the shortest paths can be found are: The Bellman-Ford algorithm, Floyd- Warshall algorithm, Johnson’s algorithm, etc.