|
|
|
|
|
在工程领域，一个大的工程项目通常被划分为许多较小的子工程（称为活动），当这些子工程都完成时，整个工程也就完成了。若以顶点表示活动，用有向边表示活动之间的优先关系，则称这样的有向图为以顶点表示活动的网（Activity On Vertex network，AOV网）。在有向网中，若从顶点νi到顶点νj有一条有向路径，则顶点νi是νj的前驱，顶点νj是νi的后继。若<νi，νj>是网中的一条弧，则顶点νi是νj的直接前驱，顶点νj是νi的直接后继。AOV网中的弧表示了活动之间的优先关系，也可以说是一种活动进行时的制约关系。
|
|
|
|
在AOV网中不应出现有向环，若存在的话，则意味着某项活动必须以自身任务的完成为先决条件，显然这是荒谬的。因此，若要检测一个工程划分后是否可行，首先就应检查对应的AOV网是否存在回路。检测的方法是对其AOV网进行拓扑排序。
|
|
|
|
|
|
拓扑排序是将AOV网中所有顶点排成一个线性序列的过程，并且该序列满足：若在AOV网中从顶点νi到νj有一条路径，则在该线性序列中，顶点νi必然在顶点νj之前。
|
|
|
|
一般情况下，假设AOV网代表一个工程计划，则AOV网的一个拓扑排序就是一个工程顺利完成的可行方案。对AOV网进行拓扑排序的方法如下：
|
|
|
|
（1）在AOV网中选择一个入度为零（没有前驱）的顶点且输出它；
|
|
|
|
|
|
（3）重复上述两步，直至网中不存在入度为零的顶点为止。
|
|
|
|
按照上述步骤进行拓扑排序的过程如下图所示，得到的拓扑序列为6，1，4，3，2，5。显然，对有向图进行拓扑排序所产生的拓扑序列有可能是多种。
|
|
|
|
|
|
|
|
执行的结果会有两种情况：一种是所有顶点已输出，此时整个拓扑排序完成，说明网中不存在回路；另一种是尚有未输出的顶点，剩余的顶点均有前驱顶点，表明网中存在回路，拓扑排序无法进行下去。
|
|
|
