C语言_数据结构_拓扑排序

顶点活动网
AOV网（Activity On Vertex Network）表示工程的有向图 用顶点表示活动，用弧表示活动之间的优先关系。

对AOV网进行拓扑排序的方法：
    1.在AOV网中选择一个入度为0的顶点且输出它
    2.从网中删除此顶点及与该顶点有关的所有边
    3重复上述两步，直至网中不存在入度为0的顶点为止。

如果不能输所有顶点 说明在图中存在环路（顶点入的为1）

入度： 指向该顶点的弧的数量
入度为0 ： 没有指向该顶点的弧

在下图中 只有v1  没有箭头指向它

至此，只是一种拓扑排序。由AOV网构造出拓扑序列的实际意义是：如果按照拓扑序列中的顶点次序，在开始每一项活动时，能够保证它的所有前驱活动都已完成，从而使整个工程顺序进行，不会出现冲突的情况。

就像秋天穿衣服一样，无论先穿秋衣、秋裤、袜子都可以，但是不能先穿外套，后穿秋衣。（或者先穿鞋子后穿袜子）。

 

以下是另几种拓扑排序

————————————————————————————————————————————————————

该图拓扑排序仅有6种