Kahn's Algorithm (Java)


  • 0
    M

    My favorite way to perform topological sorts is Kahn's algorithm. You just have to make sure you keep track of the # of totalEdges + incomingEdges w/ O(1) access time to keep it fast.

    class Solution {
        
        public int[] findOrder(int numCourses, int[][] preqs) {
            
            // If remaining edges then return empty
            
            int totalEdges = 0;
            
            int[] incomingEdges = new int[numCourses];
            
            HashMap<Integer, ArrayList<Integer>> edges = new HashMap<Integer, ArrayList<Integer>>();
            
            for(int i=0;i<numCourses;i++){
                
                edges.put(i, new ArrayList<Integer>());
                
            }
            
            for(int[] req: preqs){
                
                edges.get(req[1]).add(req[0]);
                
                incomingEdges[req[0]]++;
                
                totalEdges++;
                
            }
            
            ArrayList<Integer> order = new ArrayList<Integer>();
            
            Queue<Integer> edgeless = new LinkedList<Integer>();
            
            for(int i=0;i<numCourses;i++) if(incomingEdges[i] == 0) edgeless.add(i);
            
            while(edgeless.size() > 0){
                
                int n = edgeless.remove();
                
                order.add(n);
                
                ArrayList<Integer> neighbors = edges.get(n);
                
                for(int neighbor: neighbors){
                    
                    incomingEdges[neighbor]--;
                    
                    totalEdges--;
                    
                    if(incomingEdges[neighbor] == 0) edgeless.add(neighbor);
                    
                }
                
            }
            
            if(totalEdges > 0) return new int[0];
            
            int[] tr = new int[order.size()];
            
            for(int i=0;i<order.size();i++) tr[i] = order.get(i);
            
            return tr;
            
        }
        
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.