偏序、全序

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

则称R是A上的偏序关系。配备了偏序关系的集合,叫偏序集合
在偏序中,只有部分元素可以在偏序关系下,进行比较。

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

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


拓扑排序

由集合的一个偏序得到一个全序。也就是 对于任何邻接自顶点u的顶点v,在最后的排序结果中,顶点u总是在顶点v的前面。
利用顶点表示活动,弧表示活动间的优先关系的有向图,叫AOV(Activity on Vertex NetWork)网。
在AOV网中不应该出现环,如果出现环,就意味着某项活动以自己为先决条件,显然是矛盾的。
进行拓扑排序的方法如下:
方法1:

方法2:

在进行DFS时,最先被访问的顶点就是出度为0的顶点,它是拓扑有序序列中的最后一个顶点。由此,DFS的访问序列就是逆向的拓扑有序序列。
但是需要注意的是:AOV网一定不是强连通图(AOV中无环,但是强连通图有环),所以,需要进行多次DFS。


代码实现

tim-chow的github