Quick Notes #1: Kahn’s Algorithm
Topological ordering is an important concept in graph theory. Topological ordering is a linear ordering of vertices of the directed acyclic graph such that for every edge from u to v, u comes before v in the ordering.
Practical applications of topological ordering:
- Dependency Management
- Package/Libraries Management
- Task Scheduling
- Finding Cycles in a graph
Note that, topological order does not exist for an undirected or cyclic graph.
There are several ways to find the topological ordering of a DAG. The standard way is to traverse the graph using DFS or BFS and add the visited notes into the stack.
Standard Implementation: https://github.com/AlokRatnaparkhi/LeetCodePractice/blob/master/Leetcode/src/TopologicalSort.java
Alternatively, there is an elegant and simple way to find the topological graph. The way is known as Kahn’s Algorithm.
Resources:
Psuedo code:
def findTopologicalOrder(Graph g){
Let indegree[] be the array to store indegrees of vertices
Let order[] be the array to store topological order
for all vertices in Graph G
{ calculate the indegrees of all vertices in G by looping through adjacency list
}
Find nodes with 0 indegree and add them to Queue
while queue is not empty{
int u=queue.pop();
order.add(u);
for all neighbors of u{
decrement the indegrees of u;
if(indegree[u]==0) add u to the queue;
}
if(order.length==number of vertices in the graph)
{return order;
}
else
{ return null; //Cycle exist in a graph
}
}
Source code (Java):
Time Complexity:
O(V+E)
Space complexity:
O(V)
