Topological Sorting in Graph Using DFS and BFS GeeksForGeeks

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

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