偏序、全序

偏序:

设 R 是集合 A 上的二元关系,若 R 满足:

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

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

全序:

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

配备了全序关系的集合,叫全序集合

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


拓扑排序

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

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

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

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

方法1:

方法2:

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

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


代码实现

tim-chow 的 Github