拓扑排序，很多人都可能听说但是不了解的一种算法。或许很多人只知道它是图论的一种排序，至于干什么的不清楚。又或许很多人可能还会认为它是一种啥排序。而实质上它是对有向图的顶点排成一个线性序列。

至于定义，百科上是这么说的：

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

为什么会有拓扑排序？拓扑排序有何作用？

举个例子，学习java系列的教程

就比如学习java系类(部分)从java基础，到jsp/servlet，到ssm，到springboot，springcloud等是个循序渐进且有依赖的过程。在jsp学习要首先掌握java基础和html基础。学习框架要掌握jsp/servlet和jdbc之类才行。那么，这个学习过程即构成一个拓扑序列。当然这个序列也不唯一，你可以对不关联的学科随意选择顺序(比如html和java可以随便先开始哪一个。)

那上述序列可以简单表示为：

其中五种均为可以选择的学习方案，对课程安排可以有参考作用，当然，五个都是拓扑序列。只是选择的策略不同！

一些其他注意：

DGA：有向无环图 AOV网：数据在顶点 可以理解为面向对象 AOE网：数据在边上，可以理解为面向过程！

而我们通俗一点的说法，就是按照某种规则将这个图的顶点取出来，这些顶点能够表示什么或者有什么联系。

规则：

正常步骤为(方法不一定唯一)：

对于上图的简单序列，可以简单描述步骤为：

这样就完成一次拓扑排序，得到一个拓扑序列，但是这个序列并不唯一！从过程中也看到有很多选择方案，具体得到结果看你算法的设计了。但只要满足即是拓扑排序序列。

另外观察 1 2 4 3 6 5 7 9这个序列满足我们所说的有关系的节点指向的在前面，被指向的在后面。如果完全没关系那不一定前后(例如1,2)

对于拓扑排序，如何用代码实现呢？对于拓扑排序，虽然在上面详细介绍了思路和流程，也很通俗易懂。但是实际上代码的实现还是很需要斟酌的，如何在空间和时间上能够得到较好的平衡且取得较好的效率？

首先要考虑存储。对于节点，首先他有联通点这么多属性。遇到稀疏矩阵还是用邻接表比较好。因为一个节点的指向节点较少，用邻接矩阵较浪费资源。

另外，如果是1，2，3，4，5，6这样的序列求拓扑排序，我们可以考虑用数组，但是如果遇到1，2，88，9999类似数据，可以考虑用map中转一下。那么，

我们具体的代码思想为：

这里主要是利用栈或者队列储存入度只为0的节点，只需要初次扫描表将入度为0的放入栈(队列)中。

至于具体demo：