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){
                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.

/*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;

    }

}