Prashant Mishra

Posted on

# Topological Sorting in Graph Using DFS and BFS GeeksForGeeks

Topological sort:
It is a linear ordering of the nodes of the graph such that if there is an edge from `u` and `v` then `u` must come before `v` in the ordering.

Note:

• Topological sorting is only applicable to directed graph.
• We can't have topological sorting if the directed graph has cycle. As it will not satisfy the definition of topological sort.

DFS Approach:
Time complexity :`O(N+E)` and space complexity is : O(N)+O(N)+O(N)+O(N) = O(N)*4 (Auxillary stack space for recursive call, N for visited array, N for result array and 4th N for Stack)

``````/*Complete the function below*/

/*Topological sorting:
* A linear ordering of vertices such that if there is an edge between u->v, then
u appears before v in the ordering
*/
class Solution
{
//Function to return list containing vertices in Topological order.
static int[] topoSort(int V, ArrayList<ArrayList<Integer>> adj)
{
//we will use depth first search for this
//we have to make sure that u appears before v , if there is
//an edge between u and v
//hence using depth first search would be a better approach.
Stack<Integer> stack = new Stack<>();
int visited[] = new int[V];
for(int i =0;i<V;i++){
if(visited[i] ==0){
}
}
int result[] = new int[V];
int index =0;
while(!stack.isEmpty()){
result[index] = stack.pop();
index++;
}
return result;
}
public static void dfs(int node, int[] visited,Stack<Integer> stack, ArrayList<ArrayList<Integer>> adj){
visited[node] = 1;
if(visited[i] ==0){
}
}
stack.push(node);
}
}
``````

BFS approach to topological sorting: Using Kahn's Algorithm
Time complexity : O(N+E) and space complexity will be O(n)*3 for inodegree array, queue, and result array.

``````/*Complete the function below*/

class Solution
{

//Function to return list containing vertices in Topological order.
static int[] topoSort(int V, ArrayList<ArrayList<Integer>> adj)
{
//we will use Kahn's algorithm for getting topological sorting, it uses
// we will be required to calculate the indegree of all the nodes;
int indegree[] = new int[V];
/// calculating indegrees of all the nodes
for(int i =0;i<V;i++){
indegree[j]++;
}
}

//putting those nodes in the queue whose indegrees are 0
//because these are the nodes that have no incoming edge to them hence they
//can be at the start of the topological sorting as it will not cause any issue
//because we are maintaining order of u followed by v where u->v (u has edge directed towards v)
for(int i =0;i<V;i++){
if(indegree[i]==0){
}
}
int result[] = new int[V];
int index =0;
while(!q.isEmpty()){
Integer i = q.remove();
result[index++] = i;
// here we re reducing the indegrees as the nodes that are alredy there
// the queue are getting removed hence there edges with the node 'node' will
//also be removed hence there indegrees will decrease by one
indegree[node]--;
//and as soon as there indegrees becomes 0 means they are independent now and they have no incoming edge to them
//hence they can be added to queue just like we did earlier.
if(indegree[node]==0){