文章目录题目解析算法原理建图入度数组代码实现题目链接207. 课程表题目解析拓扑排序Topological sorting要解决的问题是如何给一个有向无环图的所有节点排序。有向无环图Directed Acyclic Graph, 缩写 DAG是一种边有方向且没有环形结构的图结构。拓扑排序的起始点是顶点入度为0的节点将顶点排序完毕后从该顶点发出的有向边全部会被删除这使得被指向的节点的入度数会减1当入度数为0时这个节点就成为新了的顶点然后下一轮从该顶点开始排序以此重复直到没有顶点为止。入度表示指向某节点的有向边数量出度表示从该节点发出的有向边数量构造拓扑序列步骤从图中选择一个入度为零的点输出该顶点从图中删除此顶点及其所有的出边重复上面两步直到所有顶点都输出拓扑排序完成或者图中不存在入度为零的点此时说明图是有环图拓扑排序无法完成陷入死锁。例子做一道青椒炒肉的过程图如下按照流程图中的顺序一步一步做出来这道菜的过程就相当于是拓扑排序的过程。拓扑排序的目标是将所有节点排序可能出现多个不同的排序结果买菜 — 准备厨具 — 洗菜 — 腌肉 — 切菜 — 炒菜 — 装盘准备厨具 — 买菜 — 洗菜 — 腌肉 — 切菜 — 炒菜 — 装盘准备厨具 — 买菜 — 洗菜 — 切菜 — 腌肉 — 炒菜 — 装盘准备厨具 — 腌肉 — 买菜 — 洗菜 — 切菜 — 炒菜 — 装盘如何实现拓扑排序借助队列一次多源 BFS 即可先将所有入度为0的节点放入队列层序遍历先拿出队首元素并添加到结果中然后将从该队首元素发出的边全部删去再判断与这些边相连的节点的入度减一之后的值是否为0若为0就再加入队列中题目给出一个numCourses表示本学期要修读的课程数记作0-numCourses-1。在选修某些课程之前需要一些先修课程。先修课程由数组prerequisites给出其中prerequisites[i] [a, b]表示如果要学习课程a则必须先学习课程b。我们需要判断能否完成所有课程的学习。例1numCourses 2, prerequisites [[1,0]]prerequisites[0] [1, 0]表示要学习课程1必须先学习课程0而总课程数numCourses 2这两门课程可能就是课程1和课程0因此可以先学习课程0再学习课程1是可能完成所有课程的学习的因此返回true。例2numCourses 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]]根据题目所给可以画出我们需要判断的 ”能否完成所有课程的学习“ 其实就是判断有向无环图中是否存在环—— 即能否进行拓扑排序。因此我们可以用拓扑排序来解决本题。构造拓扑序列步骤从图中选择一个入度为零的点输出该顶点从图中删除此顶点及其所有的出边重复上面两步直到所有顶点都输出拓扑排序完成或者图中不存在入度为零的点此时说明图是有环图拓扑排序无法完成陷入死锁。建图在构造拓扑序列之前首先要根据题目抽象出图结构。我们用邻接表来表示图的结构代码实现有两种方式对于字符串类型的数据我们通常用哈希表Map String, List String edges作为邻接表来映射 ”节点相连的节点列表“。对于整数类型的数据我们通常用链表List List Integer edges作为邻接表用下标前提是数据从0开始计数作为 ”节点“链表的值作为 ”与该节点相连的节点列表“。也可以使用哈希表来映射Map Integer, List Integer edges入度数组本题我们在进行拓扑排序的过程中还需要知道节点的入度值因此我们为了方便可以用一个入度数组in来记录图中所有节点的入度值。int[]innewint[numCourses];代码实现classSolution{publicbooleancanFinish(intnumCourses,int[][]prerequisites){// 顶点, 连接的节点列表MapInteger,ListIntegeredgesnewHashMap();// 邻接表存放图int[]innewint[numCourses];// 用于记录每一个顶点的入度值// 建图for(int[]prerequisite:prerequisites){// prerequisites[a][b] - 要学习a必须先学习b - b是a的前提/b有一条路径指向aintaprerequisite[0],bprerequisite[1];// b - aif(!edges.containsKey(b)){// 判断邻接表中是否存在顶点(b)edges.put(b,newArrayList());// 将顶点存入邻接表中}edges.get(b).add(a);// 将与顶点连接的节点添加到节点列表in[a];// 更新连接b节点的入度值}// 拓扑排序(用来判断图中是否存在环:存在-true/不存在-false)QueueIntegerqueuenewArrayDeque();// 队列用于存放入度值为0的顶点// 1.将入度值为0的顶点放入队列for(intx0;xnumCourses;x){if(in[x]0){queue.offer(x);}}// 2.层序遍历/BFSwhile(!queue.isEmpty()){inttopqueue.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;}}完