Topological Sort (Using BFS & DFS)
Amrit Raj
1353
Topological SortCareer

What is Topological Sort ?

Lineary Ordering of vertices such that if there is edge between U & V then U must appears before V in that   
Ordering.
It only exist on Directed Acyclic Graph (DAG).

Below are the code of topological sort of a graph using DFS & BFS Algorithm

Using DFS

Approach

  • Create a Visited array.
  • Create a Stack
  • And Loop from i = 0 to i < V and check if ith vertex visited or not if not then call dfs for that vertex.
  • If dfs call is over then add that vetex in the stack
  • Create an answer arr and add elements in it from stack and return arr.
class Solution
{   
    static void dfs(int i, boolean[] vis, Stack<Integer> st, ArrayList<ArrayList<Integer>> adj){
        vis[i] = true;
        
        for(int it : adj.get(i)){
            if(!vis[it]) dfs(it, vis, st, adj);
        }
        
        st.push(i);
    }
    static int[] topoSort(int V, ArrayList<ArrayList<Integer>> adj) 
    {
        Stack<Integer> st = new Stack<Integer>();
        boolean[] vis = new boolean[V];
        int[] ans = new int[V];
        
        for(int i = 0; i < V; i++){
            if(!vis[i]){
                dfs(i, vis, st, adj);
            }
        }
        int i = 0;
        while(!st.isEmpty()){
            int elem = st.peek();
            st.pop();
            ans[i++] = elem;
        }
        
        return ans;
    }
}

Using BFS (Khan's Algorithm)

Approach

  • Find indegree of every vertex and add it into some array (indegree in this solution).
  • add all vertex havind indegree 0 in the queue.
  • remove vertex from queue and add it to ans array after that remove all directed edges of that vertex
  • after remove edges if indegree will become 0 for some vertex then add that vertex to queue
class Solution
{   
    static int[] topoSort(int V, ArrayList<ArrayList<Integer>> adj) 
    {
        Queue<Integer> q = new LinkedList<>();
        int[] indegree = new int[V];
        
        // finding indegree of nodes
        for(int i = 0; i < V; i++){
            for(int it : adj.get(i)){
                indegree[it]++;
            }
        }
        
        // add nodes having 0 indegree
        for(int i = 0; i < V; i++){
            if(indegree[i] == 0){
                q.add(i);
            }
        }
        int i = 0;
        int[] topo = new int[V];
        // BFS
        while(!q.isEmpty()){
            int node = q.peek();
            q.remove();
            topo[i++] = node;
            
            for(int it : adj.get(node)){
                indegree[it]--;
                if(indegree[it] == 0) q.add(it);
            }
        }
        
        return topo;
    }
}
Comments (0)