LeetCode 210：课程表 II （拓扑排序）

LeetCode 210

题目：

方法一：DFS

拓扑排序理论
仅在判断是否成环基础上增加了一个list用于记录；
使用后序遍历，当遍历到末尾时再开始自底向上记录节点存于list，所以list中节点顺序和排序遍历相反，需要Collections.reverse或者使用栈来存；

注意：

1. 递归到头才开始记录，所以是后续遍历
2. Queue和Stack都有size()方法，继承于Collection和Vector
3. 终止条件在标记marked和onPath之前，且 onPath在marked之前！

class Solution {
    boolean isCycle=false;
    List<Integer> list=new ArrayList<>();
    boolean[] marked;
    boolean[] onPath;
    
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph=buildGraph(prerequisites,numCourses);
        marked=new boolean[numCourses];
        onPath=new boolean[numCourses];
        for(int i=0;i<numCourses;i++){ //遍历顶点
            dfs(graph,i);
        }
        if(isCycle){
            return new int[]{};
        }
        int n=list.size();
        int[] r=new int[n];
        Collections.reverse(list);
        for(int i=0;i<n;i++){
            r[i]=list.get(i);
        }
        return r;
    }

    List<Integer>[] buildGraph(int[][] prerequisites,int numCourses){
        List<Integer>[] graph=new List[numCourses];
        for(int i=0;i<numCourses;i++){
            graph[i]=new LinkedList<Integer>();
        }
        for(int[] k:prerequisites){
            int pre=k[1];
            int follow=k[0];
            graph[pre].add(follow);
        }
        return graph;
    }   

    void dfs(List<Integer>[] graph,int s){
        //终止条件, onPath在marked 之前 ！
        if(onPath[s]){
            isCycle=true;
            return;
        }
        if(marked[s]){
            return ;
        }
        marked[s]=true;
        onPath[s]=true;
        for(int k:graph[s]){ //遍历邻接表
            dfs(graph,k);
        }
        list.add(s); // 后续遍历 ！
        onPath[s]=false;    
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

或者用栈来记录：

		int n=stack.size();
        int[] r=new int[n];
        for(int i=0;i<n;i++){
            r[i]=stack.pop();
        }
        return r;
1
2
3
4
5
6

方法二：BFS

弹出节点的顺序即为拓扑排序结果 ！

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
  List<Integer>[] graph=buildGraph(prerequisites,numCourses);
        //入度数组
        int[] indegree=new int[numCourses]; //int数组会自动初始化为0
        for(int[] k:prerequisites){
            int from=k[1]; //先修课程from
            int to=k[0]; // 后续课程to即被指的元素，from指向to,to被指的次数即入度
            indegree[to]++;  //入度数量++
        }

        //如果入度为0，才可以作为BFS的起点 ！
        Queue<Integer> nodes=new LinkedList<>();
        for(int i=0;i<numCourses;i++){
            if(indegree[i]==0){
                nodes.add(i);
            }
        }
        int count=0;
        int[] r=new int[numCourses];
        //BFS
        //start是入度为0的点，即不被依赖
        //没有额外的target，nodes遍历完则结束
        while(!nodes.isEmpty()){
            int temp=nodes.poll(); // 1.弹出节点
            // 弹出节点的顺序即为拓扑排序结果
            r[count]=temp;
            count++;
            for(int k :graph[temp]){ // 遍历temp的邻接表的每个元素，相当于遍历temp节点下面这一层 ！
                indegree[k]--;
                if(indegree[k]==0){ //2. 当邻接表中有元素入度为0了，添加节点
                    nodes.add(k);
                }
            }
        }
        if(count!=numCourses){ //如果成环
            return new int[]{};
        }
        return r;


    }


    List<Integer>[] buildGraph(int[][] prerequisites,int numCourses){
        List<Integer>[] graph=new List[numCourses];
        for(int i=0;i<numCourses;i++){
            graph[i]=new LinkedList<Integer>();
        }
        for(int[] k:prerequisites){
            int pre=k[1];
            int follow=k[0];
            graph[pre].add(follow);
        }
        return graph;
    }   
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59