|
顶点活动的网(也称AOV-网)是用顶点表示活动、用弧表示活动优先关系的有向图。在网中,如果从顶点i到顶点j有一条有向路径,则称i是j的前驱,j是i的后继。若是网中的一条弧,则i是j的直接前驱,j是i的直接后继。
|
|
|
在AOV-网中,不应存在环,因某项活动不应以它自己为先决条件,故对给定的AOV-网,可采用对有向图构造其顶点的拓扑有序序列来监测其是否存在环。拓扑有序序列是AOV-网中的顶点所构成的有序序列T=(l,…,I,…,n),且满足以下条件:
|
|
|
.AOV-网的优先关系与序列所反映的先后关系一致;
|
|
|
.在AOV-网中无优先关系的顶点也被赋予了一定的先后关系。
|
|
|
则称序列T为AOV-网的一个拓扑有序序列,对AOV-网构造它的拓扑有序序列的过程叫作拓扑排序。
|
|
|
若网中的所有顶点都在它的拓扑有序序列中,则该AOV-网中必定不存在环。
|
|
|
|
(1)在有向图中选择一个没有前驱(即入度为0)的顶点并输出。
|
|
|
|
(3)重复执行上述步骤(1)和(2),直到全部顶点都已输出或图中已没有无前驱的顶点。
|
|
|
拓扑排序方法是关键路径求解问题等的基础,同时可应用于课程计划的制订等。从拓扑排序构造的方法可见拓扑排序本质上就是图的遍历过程。
|
|
|