【BFS 解决拓扑排序】课程表

文章目录

• 题目解析
• 算法原理
• • 建图
  • 入度数组
• 代码实现

题目链接：207. 课程表

---

题目解析

拓扑排序（Topological sorting）要解决的问题是如何给一个有向无环图的所有节点排序。

有向无环图（Directed Acyclic Graph, 缩写 DAG），是一种边有方向且没有环形结构的图结构。

拓扑排序的起始点是顶点（入度为0的节点），将顶点排序完毕后，从该顶点发出的有向边全部会被删除，这使得被指向的节点的入度数会减1，当入度数为0时这个节点就成为新了的顶点，然后下一轮从该顶点开始排序，以此重复，直到没有顶点为止。

• 入度：表示指向某节点的有向边数量，
• 出度：表示从该节点发出的有向边数量

构造拓扑序列步骤：

1. 从图中选择一个入度为零的点
2. 输出该顶点，从图中删除此顶点及其所有的出边

重复上面两步，直到所有顶点都输出，拓扑排序完成，或者图中不存在入度为零的点，此时说明图是有环图，拓扑排序无法完成，陷入死锁。

例子：做一道青椒炒肉的过程图如下

按照流程图中的顺序一步一步做出来这道菜的过程，就相当于是拓扑排序的过程。

拓扑排序的目标是将所有节点排序，可能出现多个不同的排序结果：

• 买菜 —> 准备厨具 —> 洗菜 —> 腌肉 —> 切菜 —> 炒菜 —> 装盘
• 准备厨具 —> 买菜 —> 洗菜 —> 腌肉 —> 切菜 —> 炒菜 —> 装盘
• 准备厨具 —> 买菜 —> 洗菜 —> 切菜 —> 腌肉 —> 炒菜 —> 装盘
• 准备厨具 —> 腌肉 —> 买菜 —> 洗菜 —> 切菜 —> 炒菜 —> 装盘

如何实现拓扑排序？借助队列，一次多源 BFS 即可：

1. 先将所有入度为0的节点放入队列
2. 层序遍历：先拿出队首元素并添加到结果中，然后将从该队首元素发出的边全部删去，再判断与这些边相连的节点的入度减一之后的值是否为0（若为0就再加入队列中）

题目给出一个numCourses表示本学期要修读的课程数，记作0-numCourses-1。

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

我们需要判断能否完成所有课程的学习。

例1：numCourses = 2, prerequisites = [[1,0]]

prerequisites[0] = [1, 0]表示要学习课程1必须先学习课程0，而总课程数numCourses = 2，这两门课程可能就是课程1和课程0，因此可以先学习课程0再学习课程1，是可能完成所有课程的学习的，因此返回true。

例2：numCourses = 5, prerequisites = [[1,0], [2,0], [3,0], [3,1], [3,2], [4,3]]

学习课程的顺序可以是：0 —> 1 —> 2 —> 3 —> 4，因此是可以完成所有课程的学习的，返回true。

---

算法原理

例：numCourses = 5, prerequisites = [[1,0], [2,0], [3,0], [3,1], [3,2], [4,3]]

根据题目所给，可以画出：

我们需要判断的 ”能否完成所有课程的学习“ 其实就是判断有向无环图中是否存在环—— 即能否进行拓扑排序。

因此我们可以用拓扑排序来解决本题。

构造拓扑序列步骤：

1. 从图中选择一个入度为零的点
2. 输出该顶点，从图中删除此顶点及其所有的出边

重复上面两步，直到所有顶点都输出，拓扑排序完成，或者图中不存在入度为零的点，此时说明图是有环图，拓扑排序无法完成，陷入死锁。

建图

在构造拓扑序列之前，首先要根据题目抽象出图结构。

我们用邻接表来表示图的结构，代码实现有两种方式：

• 对于字符串类型的数据，我们通常用哈希表（Map < String, List < String >> edges）作为邻接表来映射 ”节点，相连的节点列表“。
• 对于整数类型的数据，我们通常用链表（List< List< Integer >> edges）作为邻接表，用下标（前提是数据从0开始计数）作为 ”节点“，链表的值作为 ”与该节点相连的节点列表“。（也可以使用哈希表来映射：Map < Integer, List < Integer >> edges）

入度数组

本题我们在进行拓扑排序的过程中还需要知道节点的入度值，因此我们为了方便，可以用一个入度数组in来记录图中所有节点的入度值。

int[]in=newint[numCourses];

---

代码实现

classSolution{publicbooleancanFinish(intnumCourses,int[][]prerequisites){// <顶点, 连接的节点列表>Map<Integer,List<Integer>>edges=newHashMap<>();// 邻接表存放图int[]in=newint[numCourses];// 用于记录每一个顶点的入度值// 建图for(int[]prerequisite:prerequisites){// prerequisites[a][b] -> 要学习a必须先学习b -> b是a的前提/b有一条路径指向ainta=prerequisite[0],b=prerequisite[1];// b -> aif(!edges.containsKey(b)){// 判断邻接表中是否存在顶点(b)edges.put(b,newArrayList<>());// 将顶点存入邻接表中}edges.get(b).add(a);// 将与顶点连接的节点添加到节点列表in[a]++;// 更新连接b节点的入度值}// 拓扑排序(用来判断图中是否存在环:存在-true/不存在-false)Queue<Integer>queue=newArrayDeque<>();// 队列用于存放入度值为0的顶点// 1.将入度值为0的顶点放入队列for(intx=0;x<numCourses;x++){if(in[x]==0){queue.offer(x);}}// 2.层序遍历/BFSwhile(!queue.isEmpty()){inttop=queue.poll();// 取出队首元素// 遍历队首元素对应的节点列表,将列表中的所有节点的入度值减一(删除连接线)for(intx:edges.getOrDefault(top,newArrayList<>())){// 将入度值减一之后判断入度值是否为0(为0时是顶点,要放入队列)if(--in[x]==0){queue.offer(x);}}}// 判断图中是否存在环(若入度数组in的所有值都为0则图中不存在环)for(intx:in){if(x!=0){// 不为0,有环returnfalse;}}// 返回truereturntrue;}}

---

完