Given a Directed Acyclic Graph (DAG) with "v" vertices (0 to v-1). Find any Topological Sorting of that Graph.
Note: A directed acyclic graph (DAG) refers to a directed graph which has no directed cycles.
Topological sorting means linear ordering of vertices such that, if there is an edge u to v, u appears before v in the ordering.
Solutions
Method 1: Using DFS
If the graph is disconnected, then call the function for individual trees (start from each non-visited node).
Start traversing the graph in a DFS manner and keep track of visited nodes in visited[] array.
Also initialise a Stack, "stack" to maintain the topological sort order.
Push an element to the stack when recursion for it and its adjacent nodes is complete.
Here we are making sure that, if there is an edge from u to v, then we will first push v into the stack and then u will be pushed. This is how topological order is maintained in the Stack.
Once all nodes are put into the stack, pop elements one-by-one and insert them into an array. This array contains elements in the correct topological order.
Complexity
The time complexity of this solution is O(v+e) and space complexity is O(v).
Method 2: Using BFS (Kahn's Algorithm)
In this method, we calculate the in-degree of all nodes and store it in an array inDegree [].
Next, initialise a queue and add nodes with "0" in-degree to it.
Iterate over the queue until it's empty and apply BFS to the queue with some conditions.
Take the top/peek node from Queue and add it to the answer [] array, then iterate over its adjacent elements and decrease the in-degree count for each of them, i.e., inDegree [in]--.
Also check if after decrement the current adjacent's in-degree has turned to "0". If so, add this adjacent element to the queue.
Complexity
The time complexity of this solution is O(v+e) and space complexity is O(v).