Java - Implementation of Kahn's Algorithm- Easy to Understand.

  • 0
    public boolean canFinish(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<>();
                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
                //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)
                    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()){
                    Integer n = S.remove();
                    HashSet<Integer> copysOfOutgoingNodesN = new HashSet<>(outgoingNodes.get(n)); //to avoid concurrentModificationException
                    for(Integer m : copysOfOutgoingNodesN){
                for (int i = 0; i < numCourses; i++) {
                    if(!incomingNodes.get(i).isEmpty() || !outgoingNodes.get(i).isEmpty()){
                        return false;
                return true;

Log in to reply

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