排课表，学拓扑排序！有趣的

前言大家好，我是bigsai。拓扑排序，很多人可能听说过但不了解的一种算法。大多数不知道的人会问这样一个问题：这是某种排序算法吗？这好像是图论算法？将线性序列排列到图的顶点。而且不一定是独一无二的。什么是拓扑排序？对有向无环图（DirectedAcyclicGraph，简称DAG）G进行拓扑排序，就是将G中的所有顶点排列成一个线性序列，使得图中任意一对顶点u和v，若边∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑序（TopologicalOrder）的序列，简称拓扑序列。简单地说，就是从某个集合上的偏序得到一个集合上的全序，这种操作称为拓扑排序。拓扑排序的作用是什么？拓扑排序有很多应用。当某些项目有多个进程时，拓扑排序可以获得有效的处理顺序，而游戏中的某些任务必须满足匹配的拓扑排序才能解锁。下一层，还有一些项目或者环境的依赖集……当然，上面的例子可能不够具体。离我们更近一点的是课程学习。比如，在学习数据结构之前，你基本上需要学习C或C++，因为数据结构需要理解并能够使用C++代码；在学习操作系统和计算机网络之前，你必须学习数据结构课程，因为它涉及到很多数据结构和算法；在学习JavaWeb开发之前，你必须学习JavaSE和HTML。两门课程；不同学院的课程差别很大，但是可以很好的衔接起来，因为课程安排满足拓扑排序。还是看不懂拓扑排序？让我举一个更详细的例子。Java系列教程部分可能有以下顺序：比如学习Java系列（部分）从Java基础，到JSP/Servlet，到SSM，再到SpringBoot，SpringCloud等，是一个循序渐进、有前提的过程.学习JSP，首先要掌握Java和HTML的基础知识。学习框架，必须掌握JSP/Servlet和JDBC。那么，这个学习过程就构成了一个拓扑序列。当然这个顺序不是唯一的，不相关的科目你可以选择顺序（比如Html和Java可以随便开始）。上述序列可以简单表示为：这五个是可选的学习方案，可以作为课程安排的参考，这五个是上述有向无环图（DAG）的拓扑序列，只是小的选择策略不同（先学Java还是HTML都无所谓，但必须满足整个顺序要求），不影响规则的顺序！对于拓扑排序，还有一些比较专业的术语需要记住：DAG：DirectedAcyclicGraphAOVNetwork：数据在顶点，顶点代表活动，边代表活动序列，可以理解作为一种面向对象。AOE网络：数据在边上，顶点代表事件，有向边代表活动，边上的权重代表活动持续时间，可以理解为面向过程。很多人不知道AOE网络是干什么用的。拓扑排序是为了解决一个项目能否按顺序进行的问题，但有时也需要解决项目完成所需的最短时间。而AOE常用于寻找关键路径（内容和算法这里不再详细介绍），图片来自https://www.cnblogs.com/svod5306/p/14723338.html）。我们今天说的拓扑排序就是在AOV中找到一个不破坏图结构的序列。对于有向无环图，需要注意图：如果A在B前面，则不存在B在A前面的路径（无法形成环路）。在拓扑序列中，相邻的两个节点只需要满足上下文关系即可，不一定需要相邻（节点只需要满足相对上下文关系即可，因此拓扑排序不一定唯一）。算法分析上面简单介绍了拓扑排序，下面详细介绍拓扑排序的方法。正常的步骤是（方法不一定唯一）：1.从DAG图中找到一个没有前驱的顶点输出。可以遍历入度为0的节点，也可以使用优先级队列来维护。2.删除从该点开始的边。删除一条边，将其指向节点的入度减1，从而找到没有前驱节点的下一个顶点。3.重复以上直到输出最后一个顶点。如果还有顶点没有输出，说明有环！对于上图的简单序列，步骤可以简述为：step1：删除节点1（或2）及其指向的边，并输出节点step2：删除节点2（或3）及其指向的边指向，输出节点step2（此处两步）：删除节点3（或4）及其指向的边，输出节点，再删除节点3（或6）其指向的边，将输出节点.step3：按照以上规则重复，直到删除所有节点。这样就完成了一个拓扑排序过程，得到了一个拓扑序列，但是这个序列不是唯一的。从算法执行过程来看，有多种选择。具体结果取决于你算法的设计，但是只要满足DAG图前后相对关系的要求即可。另外，观察12436578这个序列满足我们说的相关节点指向前面，the指向后面。如果完全没关系，也不一定是前后（比如1、2）代码实现对于拓扑排序，如何用代码实现呢？上面虽然详细介绍了思路和过程，也很容易理解，但实际上代码的实现还是很有必要考虑如何在空间和时间上取得更好的平衡和更好的效率？首先，考虑存储。对于节点，它们应该存储在邻接矩阵还是邻接表中？通常，如果使用矩阵存储，拓扑排序会更有效。稀疏，浪费内存空间，这里我们还是使用邻接表来存储节点。另外，如果图中的节点是按顺序编号的，比如1,2,3,4,5,6，我们可以直接用数组，但是如果遇到1,2,88,9999类似的不连续跨度，节点编号很大，也可以考虑使用Map存储来映射位置。那么我们具体的代码思路是：①新建一个节点类，包括节点值及其指向的节点集合（这里直接使用List集合）②初始化一个个人节点数组，输入/枚举节点之间的关系，将指向的节点录入学历+1！(例如A—>C)，则C的入度为+1；③扫描所有节点（这里扫描数组）。将入度为0的所有点添加到容器堆栈（队列）中。④当栈（队列）不为空时，抛出其中任意一个节点（只要入度为零，可以随意选择顺序）。输出该节点，将该节点指向的所有节点的入度减1，如果某个点的入度减为0，则将其加入栈（队列）。⑤重复以上操作，直到栈（队列）为空。这里栈或队列主要用来存放入度为0的节点，只需要初始扫描表就可以将入度为0的节点放入栈（队列）中。因为节点之间存在关联，如果一个节点想要入度为0，那么它的前驱节点必须在它之前的入度为0。去掉关联的箭头，将自己的入度减1。在有向无环图中，总会有多个入度为0的节点。在具体实现上，有多种方法。这只是一个简单的演示，效率可能不会很高。你可以参考一下。具体实现代码为：importjava.util.ArrayDeque;importjava.util.ArrayList;importjava.util.List;importjava.util.Queue;importjava.util.Stack;publicclasstuopu{staticclassnode{intvalue;Listnext;publicnode(intvalue){this.value=value;next=newArrayList();}publicvoidsetnext(Listlist){this.next=list;}}publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubnode[]nodes=newnode[9];//存储节点inta[]=newint[9];//以度数存储Listlist[]=newArrayList[10];//临时空间，以便存储集合指向for(inti=1;i<9;i++){nodes[i]=newnode(i);list[i]=newArrayList();}initmap(nodes,list,a);//主进程//队列q1=newArrayDeque();Stacks1=newStack();for(inti=1;i<9;i++){//System.out.print(nodes[i].next.size()+"55");//System.out.println(a[i]);if(a[i]==0){s1.add(nodes[i]);}}while(!s1.isEmpty()){noden1=s1.pop();//抛出输出System.out.print(n1.value+"");Listnext=n1.next;为了(inti=0;i[]list,int[]a){list[1].add(3);nodes[1].setnext(list[1]);a[3]++;list[2].add(4);list[2].add(6);节点[2].setnext(列表[2]);a[4]++;a[6]++;列表[3].add(5);节点[3].setnext(列表[3]);a[5]++;list[4].add(5);list[4].add(6);nodes[4].setnext(list[4]);a[5]++;a[6]++;list[5].add(7);nodes[5].setnext(list[5]);a[7]++;list[6].add(8);nodes[6]。setnext(list[6]);a[8]++;list[7].add(8);nodes[7].setnext(list[7]);a[8]++;}}输出结果24613578当然，上面说的栈和队列都可以用！如果用队列的话，会得到一个12345678的拓扑序列。至于图的构建，因为没有条件，效率可能不高，算法也可能不完善.如有优化错误请指正！拓扑排序找环前面说过，拓扑排序需要一个有向无环图来得到一个拓扑序列，但是如果给定一个有向图，你怎么知道它能否构成一个拓扑序列呢？当然是拓扑排序算法的一个变化。当我们进行拓扑排序时，我们会删除所有入度为0的节点，但是如果有环，删除的节点数会小于所有节点数。在具体实现上，我们只需要在栈或者队列抛出的时候，用一个计数器来统计个数就可以了。当然这道题有207的原题，你可以看看你的code能不能ac。问题描述：你这学期必须修numCourses门课，记为0到numCourses-1。在参加某些课程之前，需要先修一些先修课程。先决条件以数组prerequisites的形式给出，其中representations[i]=[ai,bi]，表示如果要学习课程ai，必须先学习课程bi。例如，先决条件课程对[0,1]表示：要学习课程0，您需要先完成课程1。你能告诉我是否有可能完成所有课程吗？如果是，则返回true；否则，返回false。上面已经给出了分析，但是在实现代码的时候更加灵活。不一定要创建节点类，只要思路清晰即可。实现代码：classSolution{publicbooleancanFinish(intnumCourses,int[][]prerequisites){intindegree[]=newint[numCourses];Listnext[]=newArrayList[numCourses];for(inti=0;iqueue=newArrayDeque<>();for(inti=0;i