Topological sorting

Undirected graph and directed graph directed graph can be divided into directed acyclic graph DAG and directed acyclic graph

   

Given a directed graph G containing n # nodes, we give an arrangement of its node numbers if:

For any directed edge (u, v) in graph G ， u ， appears in front of v in the arrangement.

Then the arrangement is called "topological ordering" of graph G

It is easy to know that a directed acyclic graph must have no topological sorting, and a directed acyclic graph may have multiple topological sorting paths.

Any DAG has at least one topological sort, and there is an algorithm for constructing the topological sort of any DAG in linear time

1. Curriculum

https://leetcode-cn.com/problems/course-schedule/

You must take numCourses this semester, marked as {0} to} numCourses - 1.

Some prerequisite courses are required before taking some courses. The prerequisite courses are given by the array  prerequisites, where  prerequisites[i] = [ai, bi], which means that if you want to learn  ai, you must learn  bi first.

For example, the prerequisite course pair [0, 1] indicates that if you want to learn course 0, you need to complete course 1 first.
Please judge whether it is possible to complete all courses? If yes, return true; Otherwise, false is returned.

The course is regarded as the vertex of the graph, and the course pair [from,to] is regarded as an edge of the graph. The representation of the graph is list < list < integer > > edge

Where edge Get (i) represents the vertex that can be reached adjacent to vertex i. Define the number of edges reaching each vertex as in degree and the number of edges emitted from each vertex as out degree. Consider which courses can be used as learning objects, that is, those vertices with in degree of 0 can be used as learning objects. Whenever a vertex is learned, the in degree of the vertex adjacent to the vertex is reduced by one. If it is zero after subtraction, it can continue to be used as learning objects.

 

/**
     * You must take numCourses this semester, marked as {0} to} numCourses - 1.
     * Some prerequisite courses are required before taking some courses. The prerequisite courses are given in the form of {prerequisites,
     * Where ， prerequisites[i] = [ai, bi]
     * Indicates that if you want to learn the course ai, you must first learn the course bi
     * For example, the prerequisite course pair [0, 1] indicates that if you want to learn course 0, you need to complete course 1 first.
     * Please judge whether it is possible to complete all courses? If yes, return true; Otherwise, false is returned.
     * */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // Count the penetration of each vertex
        int[] nums = new int[numCourses];
        // Relationship between storage edges
        List<List<Integer>> edge = new ArrayList<>();
        for (int i=0; i<numCourses; i++) {
            edge.add(new ArrayList<>());
        }
        for (int i=0; i<prerequisites.length; i++) {
            // Handle an edge from -- > to from node list, add a node to in degree plus one
            int from = prerequisites[i][1];
            int to = prerequisites[i][0];
            List<Integer> list = edge.get(from);
            list.add(to);
            nums[to]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        // Add all points with zero degree into the collection. These points can be learned directly without prerequisite courses
        for (int i=0; i<numCourses; i++) {
            if (nums[i] == 0) {
                queue.add(i);
            }
        }
        while (!queue.isEmpty()) {
            // Learn the course index by subtracting the point entry adjacent to the course index by one
            int index = queue.poll();
            List<Integer> list = edge.get(index);
            for (int l: list) {
                // Reduce l by one
                nums[l]--;
                // If l is zero, l is added to the queue and can be used as the next learning course
                if (nums[l] == 0) {
                    queue.add(l);
                }
            }
        }
        // If there are more than zero courses, it means that you can't finish all your studies
        for (int i=0; i<numCourses; i++) {
            if (nums[i] != 0) return false;
        }
        return true;
    }

2. Schedule II

https://leetcode-cn.com/problems/course-schedule-ii/

 

Now you have a total of N courses to choose, recorded as ， 0 ， to ， n-1.

Some prerequisite courses are required before taking some courses. For example, to learn course 0, you need to complete course 1 first. We use a match to represent them: [0,1]

Given the total number of courses and their prerequisites, return the learning order you arranged to complete all courses.

There may be multiple correct orders. You just need to return one. If it is not possible to complete all courses, an empty array is returned.

Don't say anything, just go to the code

The queue is used to simulate the whole learning process. Each time the vertex with zero penetration is selected for learning. After learning the vertex, the penetration of the adjacent vertex shall be reduced by one. If it is zero after reducing one, you can continue to join the queue for direct learning.

/**
     * Now you have a total of N courses to choose, recorded as ， 0 ， to ， n-1.
     * Some prerequisite courses are required before taking some courses. For example, to learn course 0, you need to complete course 1 first,
     * We use a match to represent them: [0,1]
     * Given the total number of courses and their prerequisites, return the learning order you arranged to complete all courses.
     * There may be multiple correct orders. You just need to return one. If it is not possible to complete all courses, an empty array is returned.
     * */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // Count the penetration of each vertex
        int[] nums = new int[numCourses];
        int[] result = new int[numCourses];
        // Relationship between storage edges
        List<List<Integer>> edge = new ArrayList<>();
        for (int i=0; i<numCourses; i++) {
            edge.add(new ArrayList<>());
        }
        for (int i=0; i<prerequisites.length; i++) {
            // Handle an edge from -- > to from node list, add a node to in degree plus one
            int from = prerequisites[i][1];
            int to = prerequisites[i][0];
            List<Integer> list = edge.get(from);
            list.add(to);
            nums[to]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        // Add all points with zero degree into the collection. These points can be learned directly without prerequisite courses
        for (int i=0; i<numCourses; i++) {
            if (nums[i] == 0) {
                queue.add(i);
            }
        }
        int order = 0;
        while (!queue.isEmpty()) {
            // Learn the course index by subtracting the point entry adjacent to the course index by one
            int index = queue.poll();
            result[order] = index;
            order++;
            List<Integer> list = edge.get(index);
            for (int l: list) {
                // Reduce l by one
                nums[l]--;
                // If l is zero, l is added to the queue and can be used as the next learning course
                if (nums[l] == 0) {
                    queue.add(l);
                }
            }
        }
        for (int i=0; i<numCourses; i++) {
            if (nums[i] != 0) return new int[]{};
        }
        return result;
    }