【LeetCode-中等题】210. 课程表 II

题目

这一题是在207题的基础上，要统计拓扑排序的顺序集合，所以只需要在207的基础上加入一个将拓扑排序的节点输出即可（有环无拓扑排序）
【LeetCode-中等题】207. 课程表

方法一：bfs

相比较207题 ，加入一个数组，用于统计拓扑排序节点，
其中拓扑排序的顺序就为队列的出队顺序

//方法一  bfs 广度优先
    public int[] findOrder(int numCourses, int[][] prerequisites) {
    
    int[] cou = new int[numCourses];//课程号入度数组

    int[] num  = new int[numCourses];//用于存储拓扑排序

    List<List<Integer>> couList = new ArrayList<>();//课程号指向的课程号集合

    Queue<Integer> queue = new LinkedList<>();//辅助队列 用于处理入度为0 的课程号

    for(int i = 0 ;i<numCourses ;i++)//给集合中课程号初始化集合
        couList.add(new ArrayList<Integer>());
   
    for(int[] pre : prerequisites){
      cou[pre[0]]++;//统计各课程的入度
      couList.get(pre[1]).add(pre[0]);//给集合中课程号设置指向课程的集合
    }

    for(int i = 0 ;i<numCourses ;i++){
      if(cou[i] == 0) queue.offer(i);//搜索第一个入度为0 的课程号  加入队列
    }
    int i = 0;//用于将拓扑排序加入到一个数组用的下标
    while(!queue.isEmpty()){
          int ids = queue.poll();
          numCourses--;//取出一个元素  就让课程号总数-1
          num[i] = ids;//拓扑排序 取出的元素加入到数组
          for(int cur : couList.get(ids)){//  couList.get(ids) 根据课程号  取出课程号指向的课程  让被指向的课程号入度 -1
              if(cou[cur] >= 1 ) cou[cur]--;
              if(cou[cur] == 0 ) queue.offer(cur);//若当前课程号入度为0  则加入队列
          }
          i++;
    }
    if(numCourses == 0)  return num;
    else return new int[0];
  }
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

方法二：dfs

相比较207题 ，加入一个数组，用于统计拓扑排序节点，
其中使用一个栈来记录遍历完的节点
拓扑排序的顺序就为栈的出栈顺序

// 方法二  dfs 深度优先
    int[] cou = null;// 设置全局变量  方便dfs使用
    int[] num = null;
    List<List<Integer>> couList = null;
    boolean valid = true;
    Deque<Integer> queue = null;
  public int[] findOrder(int numCourses, int[][] prerequisites) {
     this.cou = new int[numCourses];//课程号标记数组

     this.queue = new LinkedList<>();//用于配合输出拓扑排序

     this.num  = new int[numCourses];//用于存储拓扑排序

     this.couList = new ArrayList<>();//课程号指向的课程号集合

    for(int i = 0 ;i<numCourses ;i++)//给集合中课程号初始化集合
        couList.add(new ArrayList<Integer>());
   
    for(int[] pre : prerequisites){
      couList.get(pre[1]).add(pre[0]);//给集合中课程号设置指向课程的集合
    }

    for(int i = 0 ; i<numCourses ;i++){
        if(cou[i] == 0)  dfs(i);//课程号标记数组对应的值等于 0  开始递归
    }

    if(queue.size() != numCourses) return new int[0]; //如果dfs完成之后  栈内元素个数不等于课程号总数  说明 拓扑排序不完整，存在环，自然不能将全部课程学习完，
    else{//否则就代表无环  可以得到完整的拓扑排序
      for(int i = 0 ; i<numCourses ; i++){
      
        num[i] = queue.pop();//将压栈的课程号取出来 放到数组里面
  
      }
    }  
      return num;
  }


  public void dfs(int i){
    cou[i] = 1;
    for(int cur : couList.get(i)){
      if(cou[cur] == 0){//课程号标记数组对应的值等于 0  继续递归
        dfs(cur);
        if(!valid) return ;  //根据标记为判断是否有环  有环说明不能得到拓扑排序 直接返回 不往下面执行了

      }else if(cou[cur] == 1){//如果搜索中存在环  将标志位设为fasle 
         valid = false;
         return;
      }
    }
    //一次遍历结束无环  就让该遍历元素位置的课程号数值置为  2  代表以该点进行dfs  无环
    cou[i] = 2;
    queue.push(i); //让该dfs完的课程压栈  为什么要压栈  因为最后的拓扑排序，就是栈的出栈顺序
  }
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