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;
}
}
Top comments (0)