Java BFS topological sort version and very easy to understand


  • 0
    D

    What are BFS topological sort and indegree? You can check the below link before you go through the code https://www.cs.usfca.edu/~galles/visualization/TopoSortIndegree.html

    The complexity as below is O(V*E) not O(V+E)

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegree = new int[numCourses];
        Queue<Integer> queue = new LinkedList<Integer>();
        // Traverse edges and count indegree(referece count) for each course
        for (int[] pre : prerequisites) {
            int preCourse = pre[1];
            int readyCourse = pre[0];
            indegree[readyCourse]++;
        }
        // Find zero degree(reference count equal to 0) at the begining
        for (int i = 0 ; i < numCourses ; i++) {
            if (indegree[i] == 0) queue.offer(i);
        }
        // Vertex
        while(!queue.isEmpty()) {
            int course = queue.poll();
            numCourses--;
            // Edge
            for (int[] pre : prerequisites) {
                if (course == pre[1]) {
                    if(--indegree[pre[0]] == 0) {
                        queue.offer(pre[0]);
                    }
                }
            }
        }
        return numCourses == 0;
    }

Log in to reply
 

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