拓扑排序

复习

1、偏序：自反、反对称、传递 全序：偏序且∀a,b∈A$/forall a,b /in A$必有aRb或bRa 2、若以图中的顶点来表示活动，有向边表示活动之间的优先关系，则这种用顶点表示活动的有向图成为AOV网（activity on vertex network）. 3、树的存储： （1）树的顺序存储（先序序列+每个结点的度数） （2）双亲链表表示法 （3）孩子表示法

拓扑有序序列

在AOV网的偏序集合下构造一个全序的拓扑序列

注意

（1） 若图中存在环，则不能是顶点满足拓扑序列 （2）一个DAG（directed acyclic graph）可能有多个拓扑序列

无前驱的顶点优先的拓扑排序算法

（1）选择没有前驱的结点输出它 （2）删除该点，并删去从该点出发的全部有向边 （3） 重复上述两步，直到不存在没有前驱的结点

无后继的顶点优先拓扑排序方法

可用逆邻接表作为G的存储结构

利用深度优先搜索遍历对DAG拓扑排序