Khan’s Algorithm:- Simplified
Kahn’s algorithm is used to find a topological ordering of the vertices in a DAG. It is based on the concept of in-degree, which is the number of incoming edges to a vertex.
Kahn’s algorithm is a method used to compute the topological order of vertices in a directed acyclic graph (DAG). It relies on the concept of In-degree, which is the count of incoming edges for each vertex.
The algorithm identifies vertices with no incoming edges (in-degree 0) as starting points for the ordering. These vertices can be processed first because they have no dependencies. To keep track of in-degrees, the algorithm uses an array called inDegree. It also uses a list called ans to store the topological order as it is constructed and a queueto manage vertices with in-degree 0.
Next, all vertices with an in-degree of 0 are added to the queue, as they can be processed immediately. The algorithm then enters a loop, where it repeatedly removes a vertex from the queue, adds it to the Sorted list, and processes its neighbors. For each neighbor, the algorithm reduces its in-degree by 1 to reflect that one of its dependencies has been processed. If a neighbor’s in-degree becomes 0, it is added to the Queue, making it ready for processing in subsequent iterations.
This process continues until the queue is empty. If all vertices have been added to the Sorted list by the end, the algorithm returns the list as the topological order. However, if some vertices remain unprocessed (i.e., the Sorted list does not contain all vertices), it indicates the presence of a cycle in the graph, which makes a topological order impossible. This systematic approach ensures that vertices are processed only after all their dependencies have been handled, making it a reliable method for topological sorting.
Intuition
The pseudocode for Kahn’s algorithm is as follows:
Get Avinov Roy’s stories in your inbox
Join Medium for free to get updates from this writer.
First, it creates an inDegree array initialized to 0 for all vertices, along with an empty answer list (ans) and an empty queue. Then, it calculates the in-degree of each node by traversing all edges. After that, all vertices with in-degree 0 are added to the queue. While the queue is not empty, it removes a node, adds it to the result list, and reduces the in-degree of all its neighbors. If any neighbor’s in-degree becomes 0, it is pushed into the queue. In the end, the ans list contains the topological order of the graph.
Analysis
The time complexity of Kahn’s algorithm is O(V+E), V where is the number of vertices and is the number of edges in the graph. The algorithm calculates the in-degree of each vertex in O(V+E)time, and each vertex is enqueued and dequeued at most once, resulting in a total time complexity of O(V+E).
The space complexity of Kahn’s algorithm is , where is the number of vertices in the graph. The algorithm maintains an array of in-degrees, a list of the topological ordering, and a queue of vertices with in-degree 0, each requiring space.
Code Snippet (Cpp):-
if you learnt something new, baangg the clap icon below.
