Topological Sorting in Graph Using DFS and BFS GeeksForGeeks
Tags: java, algorithms, graph
Published: 2022-07-24 02:32:00

**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<Integer>)
```java
/*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){
				dfs(i,visited,stack,adj);
			}
		}
		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;
		for(Integer i: adj.get(node)){
			if(visited[i] ==0){
				dfs(i,visited,stack,adj);
			}
		}
	    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.

```java
/*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 
		//breadh first search algorithm
		// 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++){
			for(Integer j : adj.get(i)){
				indegree[j]++;
			}
		}
		
		Queue<Integer> q = new LinkedList<>();
		//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){
				 q.add(i);
			}
		}
		int result[] = new int[V];
	    int index =0;
		while(!q.isEmpty()){
			Integer i = q.remove();
			result[index++] = i;
			for(Integer  node : adj.get(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){
					q.add(node);
				}
			}
		}
		return result;
		
    }

}
```