简述图之拓扑排序

要想知道什么是拓扑排序，那首先得有数学功底嘛，所以我们先来说说离散数学中的偏序和全序的概念。

偏序： 集合内只有部分元素之间在这个关系下是可以比较的
比如：比如复数集中并不是所有的数都可以比较大小，那么“大小”就是复数集的一个偏序关系

全序： 集合内任何一对元素在在这个关系下都是相互可比较的
比如：有限长度的序列按字典序是全序的～（最常见的是单词在字典中是全序的）

当然我们来看看标准定义：
偏序的定义：
设R是集合A上的一个二元关系，若R满足：
Ⅰ 自反性： 对任意x∈A，有xRx；
Ⅱ 反对称性（即反对称关系）： 对任意x,y∈A，若xRy，且yRx，则x=y；
**Ⅲ 传递性：**对任意x, y,z∈A，若xRy，且yRz，则xRz。
则称R为A上的偏序关系。

全序的定义：
设集合X上有一全序关系，如果我们把这种关系用 ≤ 表述，则下列陈述对于 X 中的所有 a, b 和 c 成立：
如果 a ≤ b 且 b ≤ a 则 a = b (反对称性)
如果 a ≤ b 且 b ≤ c 则 a ≤ c (传递性)
a ≤ b 或 b ≤ a (完全性)

当然了全序关系必然是偏序关系

了解了偏序，全序关系，现在来说说拓扑排序了。
拓扑排序： 简单地说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作就称之为拓扑排序。

那么拓扑排序有啥用呢？为啥要有它呢？这就是重点了。
一个表示偏序的有向图可用来表示一个流程图，它或者是一个施工流程图，或者是一个产品生产的流程图，又或者是一个数据流图（每个顶点表示一个过程），图中的每一条边表示两个子工程之间的次序关系（领先关系）。这种使用顶点表示活动，用弧（边）表示活动间的优先关系的有向图称为顶点表示活动的网（Activity On Vertrx Network），简称AOV网。在网中，若顶点 i 到顶点 j 有一条有向路径，则 i 是 j 的前驱；j 是 i 的后继。若<i,j>是网中的一条弧，则i是j的直接前驱；j是i的直接后继。

在AOV网中，不应该存在有向环，某项活动的先决条件是它本身，这是矛盾的。因此我们先得检查图中是否存在有向环。那么检测的办法就是对有向图构造其顶点的拓扑有向序列，若序列中所有顶点都在，则必然不存在环。

于是乎，构造这个拓扑有向序序列的方法就是拓扑排序。

到底怎样进行拓扑排序呢？

拓扑排序的步骤：
1、在有向图中选择一个没有钱去的顶点且输出它；
2、从图中删除该顶点和所有以它为尾的弧；
3、重复上面的两步，直到所有的顶点均已输出，或者当前图中不存在无前驱的顶点为止，其实后者就说明图中存在环。

举个例子，例如下图：

我们按照拓扑排序的步骤来写出该图的一个拓扑有序序列：
（1）找到没有前驱的顶点V1或者V6并输出，我们就选V6吧。
（2）删除V6以及以V6为尾的弧。注意（弧的箭头处为弧头，没有箭头的一端为弧尾）

（3）找到没有前驱的顶点V1，输出并删除

（4）找到V4，输出并删除

（5）找到V3，输出并删除

（6）找到V2，输出并删除

最后得到该图的一个拓扑有序序列为：