|
|
|
顶点活动的网（也称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），直到全部顶点都已输出或图中已没有无前驱的顶点。
|
|
|
|
拓扑排序方法是关键路径求解问题等的基础，同时可应用于课程计划的制订等。从拓扑排序构造的方法可见拓扑排序本质上就是图的遍历过程。
|
|
|
