LeetCode - 207 课程表

亦凉 2023-09-23 14:54 49阅读 0赞

**目录**

题目来源

题目描述

示例

提示

题目解析

算法源码

--------------------

### 题目来源 ###

[207. 课程表 - 力扣（LeetCode）][207. _ - _LeetCode]

### 题目描述 ###

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites\[i\] = \[ai, bi\] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

例如，先修课程对 \[0, 1\] 表示：想要学习课程 0 ，你需要先完成课程 1 。  
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

### 示例 ###

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:65px;">输入</td> 
   <td style="width:433px;">numCourses = 2, prerequisites = [[1,0]]</td> 
  </tr> 
  <tr> 
   <td style="width:65px;">输出</td> 
   <td style="width:433px;">true</td> 
  </tr> 
  <tr> 
   <td style="width:65px;">说明</td> 
   <td style="width:433px;">总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。</td> 
  </tr> 
 </tbody> 
</table>

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:64px;">输入</td> 
   <td style="width:434px;">numCourses = 2, prerequisites = [[1,0],[0,1]]</td> 
  </tr> 
  <tr> 
   <td style="width:64px;">输出</td> 
   <td style="width:434px;">false</td> 
  </tr> 
  <tr> 
   <td style="width:64px;">说明</td> 
   <td style="width:434px;">总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。</td> 
  </tr> 
 </tbody> 
</table>

### 提示 ###

*  1 <= numCourses <= 105
 *  0 <= prerequisites.length <= 5000
 *  prerequisites\[i\].length == 2
 *  0 <= ai, bi < numCourses
 *  prerequisites\[i\] 中的所有课程对 互不相同

### 题目解析 ###

我们可以根据题目要求画出一个有向图，比如下面用例

numCourses = 4, prerequisites = \[\[2,1\], \[4,3\], \[4,2\]\]

![2a8116fe388a47bfb89bb59aaa6c55c7.png][]

学2之前，必须先学1；

学4之前，必须先学2，3

学1，3没有前置课程。

因此，通过上面有向图，我们可以得出，能够学完所有课程。

而上面有向图其实就是一种拓扑结构，在拓扑结构中，每一个顶点都有“入度”概念，所谓入度，即当前顶点的直接前驱顶点数目

![0da1165b3e6a4b21856c92ada3daf032.png][]

如上图所示，

顶点1的入度为0

顶点2的入度为1

顶点3的入度为0

顶点4的入度为2，注意入度指的是当前顶点的直接前驱顶点个数，而顶点4的直接前驱只有2，3，因此顶点4的入度为2 。

因此，在处理以上拓扑结构时，我们的入手点，就是入度为0的顶点。

我们假设一个顶点入度为0，表示已经读完了该课程，因此我们假设去掉该顶点，则剩余顶点的入度需要被更新，如下图，1，3顶点被去除后，2的入度更新为0，4的入度更新为1

![5ceba15862b94c4f8dc5555ba3c80f28.png][]

因此，我们可能又会得到一批新的入度为0的顶点，然后重复以上步骤，直到没有入度为0的顶点，此时，若拓扑结构中，没有残留顶点，则说明，所有课程已经被读完，否则说明无法读完所有课程，比如下面用例

numCourses = 4, prerequisites = \[\[2,1\], \[3,2\], \[4,3\], \[2,4\]\]

![9f2b68c128bf4038a9e04802866fc4b8.png][]

![dc8fa8f8f5a047e3892c784dd5eb4308.png][]

当我们去除一个入度为0的顶点后，剩余顶点的入度没有为0的了，因此无法再去除顶点了，此时出现了环。

在了解了拓扑排序的基本知识后，我们就可以考虑如何实现以上过程：

首先，我们需要记录每一个顶点的入度，即每一个顶点的直接前驱的个数

然后，我们还需要记录每一个顶点A的直接后继顶点，因为，当顶点A的入度变为0时，模拟去除顶点A，即将顶点A的直接后继顶点们的入度减去1。

在统计完以上信息后，我们就可以遍历所有顶点，找到入度为0的，作为入口条件，运行减度逻辑。

### 算法源码 ###

/**
     * @param {number} numCourses
     * @param {number[][]} prerequisites
     * @return {boolean}
     */
    var canFinish = function (numCourses, prerequisites) {
      const inDegree = new Array(numCourses).fill(0); // 每个顶点的入度
      const next = {}; // 每个顶点的后继
    
      for (let [a, b] of prerequisites) {
        next[b] ? next[b].push(a) : (next[b] = [a]); // b顶点的后继是a
        inDegree[a]++; // a顶点入度+1
      }
    
      const stack = [];
    
      for (let i = 0; i < numCourses; i++) {
        // 如果i顶点的入度为0，则放入stack中
        if (inDegree[i] === 0) {
          stack.push(i);
        }
      }
    
      let count = 0; // 已学完的课程数
      while (stack.length) {
        const b = stack.pop(); // 入度为0的顶点b，表示学完了b课程
        count++;
    
        next[b]?.forEach((a) => {
          if (--inDegree[a] === 0) stack.push(a);
        });
      }
    
      return count === numCourses; // 如果已学完的课程数等于总课程数，表示已经学完
    };

![e434263337ac468ea6e66a4ccaf5b392.png][]

[207. _ - _LeetCode]: https://leetcode.cn/problems/course-schedule/
[2a8116fe388a47bfb89bb59aaa6c55c7.png]: https://img-blog.csdnimg.cn/2a8116fe388a47bfb89bb59aaa6c55c7.png
[0da1165b3e6a4b21856c92ada3daf032.png]: https://img-blog.csdnimg.cn/0da1165b3e6a4b21856c92ada3daf032.png
[5ceba15862b94c4f8dc5555ba3c80f28.png]: https://img-blog.csdnimg.cn/5ceba15862b94c4f8dc5555ba3c80f28.png
[9f2b68c128bf4038a9e04802866fc4b8.png]: https://img-blog.csdnimg.cn/9f2b68c128bf4038a9e04802866fc4b8.png
[dc8fa8f8f5a047e3892c784dd5eb4308.png]: https://img-blog.csdnimg.cn/dc8fa8f8f5a047e3892c784dd5eb4308.png
[e434263337ac468ea6e66a4ccaf5b392.png]: https://img-blog.csdnimg.cn/e434263337ac468ea6e66a4ccaf5b392.png