偏序、全序

偏序：

设 R 是集合 A 上的二元关系，若 R 满足：

• 自反性：
  若 x 属于 A，则 x R x
• 反对称性：
  若 x，y 属于 A，且 x R y、y R x，则 x = y
• 传递性：
  若 x，y，z 属于 A，且 x R y、y R z，则 x R z

则称 R 是 A 上的偏序关系。配备了偏序关系的集合，叫偏序集合。

在偏序集合中，只有部分元素可以在偏序关系下进行比较。

全序：

设 <= 是集合 A 上的全序关系，那么对于集合 A 中的任意元素 a，b，c，以下陈述都成立：

• 反对称性：
  若 a <= b，且 b <= a，则 a = b
• 传递性：
  若 a <= b，且 b <= c，则 a <= c
• 完全性：
  a <= b 或 b <= a

配备了全序关系的集合，叫全序集合。

在全序集合中，集合中的任意两个元素都可以在全序关系下进行比较。

拓扑排序

拓扑排序是由集合的一个偏序得到一个全序。即对于任何邻接自顶点 u 的顶点 v，在最后的排序结果中，顶点 u 总是在顶点 v 的前面。

利用顶点表示活动、弧表示活动间的优先关系的有向图，叫 AOV 网（Activity on Vertex NetWork）。

在 AOV 网中不应该出现环，出现环意味着某项活动以自己为先决条件，这显然是矛盾的。

进行拓扑排序的方法如下：

方法1：

• 将有向图中，所有入度为 0 的顶点，加入到 stack 中（该 stack 专门用来维护入度为 0 的顶点）

  • 当使用邻接表表示法时，可以在头结点维护入度：当添加以该顶点为弧头的弧时，将入度增加 1；当删除以该顶点为弧头的弧时，将入度减少 1

• 重复执行下面的步骤，直到 stack 为空：

  • 弹出栈顶的顶点，并访问之
  • 删除所有以该顶点为弧尾的弧
  • 判断所有被删除的弧的弧头的入度，如果为 0，则将其加入到 stack

方法2：

进行 DFS 时，发生回溯的顶点必然不存在后继节点，因此回溯序列的逆序列就是拓扑序列。

但是需要注意：AOV 网一定不是强连通图，所以可能需要进行多次 DFS。

代码实现

tim-chow 的 Github