拓扑排序的流程图

由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止：选择一个入度为0的顶点并输出之；从网中删除此顶点及所有出边。

循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。

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

拓扑排序算法

对AOV 网进行拓扑排序的方法和步骤是：

1、从AOV 网中选择一个没有前驱的顶点(该顶点的入度为0)并且输出它;

2、从网中删去该顶点，并且删去从该顶点发出的全部有向边;

3、重复上述两步，直到剩余的网中不再存在没有前驱的顶点为止。

这样操作的结果有两种：一种是网中全部顶点都被输出，这说明网中不存在有向回路;另一种就是网中顶点未被全部输出，剩余的顶点均不前驱顶点，这说明网中存在有向回路。

以下图(a)中的有向图为例，图中v1，和v6...

照着这个图

1.选一个只有出度(没有前驱的)顶点输出

2.从图中删除该顶点和所有以它为尾的(和它相连的)弧

重复上述步骤直到全部顶点都输出,得到的即是拓扑有序序列

要根据流程与需求进行设定。

标签：流程图,拓扑,排序