Java - Easy to Understand Implementation of Kahn's Algorithm


  • 0
    M
    public int[] findOrder(int numCourses, int[][] prerequisites) {
                //represent the graph using incoming and outgoing nodes map
                Map<Integer, Set<Integer>> outgoingNodes = new HashMap<>();
                Map<Integer, Set<Integer>> incomingNodes = new HashMap<>();
                
                //Initialize
                for (int i = 0; i < numCourses; i++) {
                    outgoingNodes.put(i, new HashSet<Integer>());
                    incomingNodes.put(i, new HashSet<Integer>());
                }
                
                //Loop through the 2D arrays [0, 1] means to take course 0 you have to take course 1 first. i.e. 0 <- 1
                for (int i = 0; i < prerequisites.length; i++) {
                    //[A, B] B is the prerequisites for A. A <- B
                    // to A, B is the incoming node
                    // to B, A is the outgoing node
                    incomingNodes.get(prerequisites[i][0]).add(prerequisites[i][1]);
                    outgoingNodes.get(prerequisites[i][1]).add(prerequisites[i][0]);
                }
                
                //Apply Kahn's algorithm
                /**
                 * 
                 L ← Empty list that will contain the sorted elements
                 S ← Set of all nodes with no incoming edge
                 while S is non-empty do
                    remove a node n from S
                    add n to tail of L
                    for each node m with an edge e from n to m do
                        remove edge e from the graph
                        if m has no other incoming edges then
                        insert m into S
                 if graph has edges then
                    return error (graph has at least one cycle)
                 else 
                    return L (a topologically sorted order)
                 */
    
                List<Integer> L = new ArrayList<>();
                Queue<Integer> S = new LinkedList<>();
                //Initialize S
                for(Map.Entry<Integer, Set<Integer>> entry : incomingNodes.entrySet()){
                    if(entry.getValue().isEmpty()){
                        S.add(entry.getKey());
                    }
                }
                
                while(!S.isEmpty()){
                    Integer n = S.remove();
                    L.add(n);
                    HashSet<Integer> copysOfOutgoingNodesN = new HashSet<>(outgoingNodes.get(n)); //to avoid concurrentModificationException
                    for(Integer m : copysOfOutgoingNodesN){
                        outgoingNodes.get(n).remove(m);
                        incomingNodes.get(m).remove(n);
                        
                        if(incomingNodes.get(m).isEmpty()){
                            S.add(m);
                        }
                    }
                }
    
                for (int i = 0; i < numCourses; i++) {
                    if(!incomingNodes.get(i).isEmpty() || !outgoingNodes.get(i).isEmpty()){
                        return new int[]{};
                    }
                }
                
                int[] l = new int[L.size()];
                for(int i = 0; i < L.size(); i++){
                    l[i] = L.get(i);
                }
                return l;
            }
    

Log in to reply
 

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