[algorithm] the course schedule is not simple -- topological sorting

 

introduction

 
>_< Now we need to arrange a timetable for the students (the learning order of the course)

But it's not that simple:
 

curriculum Precursor course
Course 0
Course 1 Course 0, course 4
Course 2
Course 3 Course 0
Course 4
Course 5 Course 3
Course 6 Course 3

 

Might as well draw a Graph and try it?

We realize that this is a directed graph
 
What we need to do is find a sequence: this sequence contains all nodes and satisfies the precursor position relationship of the directed graph
 
——This is topology sorting

 
 
 

definition

   topological sorting of a Directed Acyclic Graph (DAG) g is to arrange all vertices in G into a linear sequence, so that any pair of vertices u and v in the graph, if the edge < u, v > ∈ E(G), u appears before v in the linear sequence. Generally, such a linear sequence is called a sequence satisfying topological order, which is called topological sequence for short. (Baidu Encyclopedia)

 
 
 

realization

Topological sorting has two typical functions:

  1. Check whether the curriculum is legal (judge whether the directed graph has rings)
  2. Sequence of courses (generate a topological sequence)

 
Next, use two examples to show the code implementation of these two typical functions.
Moreover, each example will be implemented with two ideas (DFS/BFS). Finally, the similarities and differences of DFS/BFS will be compared.

 
 
Function 1 -- judge whether there are rings in a directed graph

Example 1:
You must take numCourse courses this semester, marked as 0 to numCourse-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, can you judge whether it is possible to complete all courses?

[DFS [implementation]
	thinking: Similar to staining, in DFS Dyeing shall be carried out in the process. If there is a closed loop, it shall be judged wrong immediately
	flag[]Array similar draw[]Array:
     		*  0   Indicates that it has not been accessed
     		*  1   Indicates that in the current DFS The path is being accessed(Pointing there again indicates a closed loop)
     		* -1   once DFS End, this point"absolute safety",That is, from this point DFS Closed loop is not possible


class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> list = new ArrayList<>();
        int[] flag = new int[numCourses];

        // Generate adjacency table according to the array (episode)
        for(int i = 0; i < numCourses; i++){
            list.add(new ArrayList<>());
        }
        for(int[] arr : prerequisites){
            list.get(arr[1]).add(arr[0]);
        }

		// DFS
        for(int i = 0; i < numCourses; i++){
            if(!DFS(list, flag, i)){
                return false;
            }
        }

        return true;

    }
	
	// DFS core code (★☆★)
    private boolean DFS(List<List<Integer>> list, int[] flag, int node){
        if(flag[node] == 1){                    // There is a closed loop in this DFS path, and the error is directly judged
            return false;
        }
        if(flag[node] == -1){                   // This node is "absolutely safe" and you do not need to start DFS from this point again
            return true;
        }
        flag[node] = 1;                         // The node point is in this ongoing DFS path
        for(int index : list.get(node)){
            if(!DFS(list, flag, index)){
                return false;
            }
        }
        flag[node] = -1;                        // DFS from node is completely over, which is "absolutely safe"
        return true;
    }
}
[BFS [implementation]
     thinking: Not used flag[]Array, but use degree[]Penetration array
      		1.Generate the in degree array while generating the adjacency table
      		2.Nodes with a penetration of 0 join the queue first
      		3.start BFS,One node is queued each time, and all adjacent nodes of the node(The node it points to)Minus one
      		4.If the entry is reduced by one and becomes 0, the node will join the queue
      		5.Count every time you join the queue+1,If the number of last queue entries is the total number of nodes, it means that all nodes are traversed once(Learned),return true

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> list = new ArrayList<>();
        int[] degree = new int[numCourses];
        int count = 0;

        // Generate adjacency table based on array
        for(int i = 0; i < numCourses; i++){
            list.add(new ArrayList<>());
        }
        for(int[] arr : prerequisites){
            list.get(arr[1]).add(arr[0]);
            degree[arr[0]]++;
        }

		// BFS core code (★☆★)
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < numCourses; i++){
            if(degree[i] == 0){
                queue.offer(i);
                count++;
            }
        }
        while(!queue.isEmpty()){
            int node = queue.poll();
            for(int index : list.get(node)){
                degree[index]--;
                if(degree[index] == 0){
                    queue.offer(index);
                    count++;
                }
            }
        }
        
        return count == numCourses;

    }
}

 

 
Function 2 - generate a topological sequence

Example 2:
You must take numCourse courses this semester, marked as 0 to numCourse-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, please give a reasonable course learning order (just give any one)?

[DFS [implementation]---- From above DFS Code conversion
	1.above DFS In the code,"Is there a ring"Is returned directly as a return value. What we need here is a sequence, and we don't need this return value,"Is there a ring"Just record with a member variable
	2.Determine one node at a time"absolute safety"When, you can put it on the stack.
	

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> list = new ArrayList<>();
        int[] flags = new int[numCourses];

        // (...) Process of generating adjacency table

        for(int i = 0; i < numCourses; i++){
            DFS(list, flags, i);
        }

		// Convert the storage stack into the final topology sequence
        if(flag){
            int i = 0;
            int res[] = new int[numCourses];
            while (!stack.isEmpty()){
                res[i++] = stack.pop();
            }
            return res;
        }else{
            return new int[0];
        }

    }

    private boolean flag = true;						// Judge whether the closed loop appears  
    Stack<Integer> stack = new Stack<>();				// Record topology sequence with stack
    
    private void DFS(List<List<Integer>> list, int[] flags, int node){
        if(flags[node] == 1){
            flag = false;
            return;
        }
        if(flags[node] == -1){
            return;
        }
        flags[node] = 1;
        for(int index : list.get(node)){
            DFS(list, flags, index);
        }
        flags[node] = -1;
        stack.put(node);
    }
}
[BFS [implementation]---- From above BFS Code conversion
	1.This transformation is very simple: Every time a node joins the queue, it is added to the record queue for storage, and finally the storage queue is transformed into a topological sequence
	2.If the length of the queue is equal to the total number of nodes, the sequence is returned; Otherwise, it means that the schedule is illegal and will be returned new int[0]


class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> list = new ArrayList<>();
        int[] degree = new int[numCourses];

        int[] res = new int[numCourses];
        int resIndex = 0;

        // Generate adjacency table based on array
        for (int i = 0; i < numCourses; i++) {
            list.add(new ArrayList<>());
        }
        for (int[] arr : prerequisites) {
            list.get(arr[1]).add(arr[0]);
            degree[arr[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (degree[i] == 0) {
                queue.offer(i);
                res[resIndex++] = i;
            }
        }
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int index : list.get(node)) {
                degree[index]--;
                if (degree[index] == 0) {
                    queue.offer(index);
                    res[resIndex++] = index;
                }
            }
        }

        return resIndex == numCourses ? res : new int[0];
    }
}

 

 
 

summary

❶ we found that DFS and BFS are two different ideas -- [DFS + staining array] VS [BFS + penetration array]

❷ the code implementation of [generate a topology sequence] can be directly modified based on the code of [directed graph ring judgment]

❸ when generating topological sequences, we should be aware of an important difference between DFS and BFS:

  1. DFS is a reverse sequence generation process. For example, 1 → 3 → 5, in DFS, recursion starts from 1, but 1 finally completes recursion. We will get 5, 3 and 1 in turn, so we use Stack for the data structure of this record sequence
  2. BFS is a process of forward generating sequence. For example, 1 → 3 → 5. In BFS, 1 with a score of 0 will join the team first, and then 3 and 5 will join the team by reducing the score to 0 in turn. We will get 1, 3 and 5 in turn, so we use Queue for the data structure of this record sequence

 
 

 

 

 

 

 

 

 

 

 
☑ Source of some topics:

[Leetcode Q207] course schedule I

[Leetcode Q210] Course Schedule II

 

End ♬

by a Lolicon ✪

Tags: Algorithm leetcode dfs bfs

Posted by noimad1 on Wed, 25 May 2022 22:41:14 +0300