LeetCode207：课程表（字节手撕算法拓扑排序）

女爷i 2023-07-25 09:48 16阅读 0赞

### 文章目录 ###

*  前言
 *  正文
 *   *  题干
     *  思路
 *  入度表（广度优先遍历）
 *   *  展示
     *  后记

# 前言 #

**（与正文无关，赶时间的跳过呀！！！）**  
前段时间了解到了这个拓扑排序，我感觉很是陌生。一百度，绝了，数据结构都学习过，想当时数据结构学习的还不错，现在都还给老师了呀，看来就算是自己学习过的内容还是需要记录和总结呀（真实废话）。  
最近在准备出一个算法第四版基础算法的记录，到时候`github`仓库发出，会将所学算法再度进行一个总结，希望能够给大家带来帮助。

# 正文 #

## 题干 ##

你这个学期必须选修 `numCourse` 门课程，记为 0 到 n`umCourse-1` 。  
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 **0** ，你需要先完成课程 **1** ，我们用一个匹配来表示他们：**\[0,1\]**。  
给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？  
**栗子**：  
1.

输入: 2, [[1,0]] 
    输出: true
    解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。

输入: 2, [[1,0],[0,1]]
    输出: false
    解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

注意：输入的先决条件是由 **边缘列表** 表示的图形，而不是 邻接矩阵 。详情请参见[图的表示法][Link 1]这里解释一下，个人看着输出的情况和介绍来看，对应的获取就是边和边之间的关系，就是前驱课程和后继课程。

## 思路 ##

**首先**对于课程来说，判断是否能够返回false和ture，需要对于输入的课程数有一个记录和判断，在完成了一门课程以后，要进行记录，同时可以以该课程为前驱，遍历到其他后面的课程，大概思想是如此。

# 入度表（广度优先遍历） #

1.  **首先我们对于给定的数组需要明白的是\[1,0\]表示的是说，对于完成课程0以后才能够完成课程，而不是课程1完成以后才能够完成0**。 所以这个时候我们举一个列子会更好理解（个人感觉之前学习过可能有点印象，蛮快就可以理解）这里进行较为细致的讲解帮助大家理解

p[][]。
    [0,1]
    [2,3]
    [1,4]
    [2,4]
    // 表示完成1以后才能够才能够完成0.完成4以后才能够完成1，2.

所以我们发现对于给定的**p**来说，p\[0\]没有出现的表示没有入度，表示不用学习其他的课程就可以进行直接的学习，这里我们进行一个记录，将他们的入度都记录下来，查看谁的入度值是0。  
2. 借助一个辅助的队列值，将上面谈到的所有的入度为0的节点放入队列里面去。  
3. 在队列不为空的时候，表示其中还存在着入度为0的节点，不可能一个课程单独的存在，所以有入度为0节点，就必然有课程阻塞在哪里。我们依次进行出队列（队列首部，先进先出），然后将对应的节点进行删除。

*  注意删除的并不是说真正的删除节点，而是说他是某个节点的前驱节点，既然此节点我们学习完成，就可以将依赖他的节点的入度减一。
 *  在减一以后若是入度为0表示它的前驱课程我们都学习完成了，所以放入到队列中。

1.  在放入到队列中的每一个值出来以后，表示入度为0的右减少以后，**numCourses**就会减一。在值达到0的时候，就表示我们的遍历是成功的，所有的课程都学习到。

public boolean canFinish(int numCourses,int [][] prerequisites){ 
            //index数组表示是说对于入度出现的次数。
            int [] index=new int [numCourses];
            List<List<Integer>> lists=new ArrayList<>();
    // 用来存放的是对应位置有多少的课程依赖于其下标值。
            Queue<Integer> queue=new LinkedList<>();
    // 队列中进入的也都是入度为0的值。
            for(int i=0;i<numCourses;i++){ 
                lists.add(new ArrayList<>());
            }
            for(int [] cp: prerequisites){ 
    // 对于每一个对应的入度++；
                index[cp[0]]++;
                lists.get(cp[1]).add(cp[0]);
            }
            for(int i=0;i<numCourses;i++){ 
                if(index[i]==0) queue.add(i);
            }
            while(!queue.isEmpty()){ 
    // 入度为0的进行取出来，看那些课程由他作为先驱。
                int current=queue.poll();
                
                for(int q: lists.get(current)){ 
                    if(--index[q]==0)
                        queue.add(q);
                }
                numCourses--;
            }
            return  numCourses==0;
        }

## 展示 ##

我们进行如下的输入

p[][]。
    [0,1]
    [2,3]
    [1,4]
    [2,4]
    // 表示完成1以后才能够才能够完成0.完成4以后才能够完成1，2.

这里我就挑出来比较难以理解的部分进行演示：  
此时对于 **lists**来说我们查看其打印：  
对于课程0来说 需要先完成下标为1的课程1。  
对于课程2来说，需要先完成下标为3的课程3.  
同理对于课程1,2来说都需要课程4的先完成。  
然后顺着代码自己梳理一遍应该能够明白具体的流程。个人觉得还是蛮绕的对于这个程序来说，需要好好思考一番。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAxNTA0Mw_size_16_color_FFFFFF_t_70]

## 后记 ##

以上就是拓扑排序的全部内容，希望大家能够在看明白的基础上进行理解和手动打一遍加深印象。

[Link 1]: https://blog.csdn.net/woaidapaopao/article/details/51732947
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAxNTA0Mw_size_16_color_FFFFFF_t_70]: /images/20230528/23b023925a264ba3b3873396984facd7.png