6. 拓扑排序

一些概念

1. 有向无环图 ： 一个有向图中不存在环，则称为有向无环图，简称 DAG
2. AOV （Activity on Vertex） ：活动在顶点上的网，是一种可形象反映出整个工程中各个活动之间的先后关系的`有向无环图。
   例如： 制作一个产品的AOV网
   AOV网

3. AOE （Activity on Edge）：活动在边上的网
   对于一个表工程的AOE网，只存在一个入度为0的顶点，称为源点，表示工程的开始；
   也只有一个出度为0的顶点，称为汇点，表示整个工程的结束。

4. 总结

拓扑排序

1. 概念：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，该序列称为该图的一个拓扑排序

   • (1) 每个顶点出现且只出现一次
   • (2) 若A在序列中排在B的前面，则在图中不存在B->A的路径

2. 对一个DAG进行拓扑排序，是将图G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若存在u到v的路径，则在拓扑排序中一定是u出现在v的前边

3. 每一个DAG图都有一个或多个拓扑排序序列

4. DAG中找到一个拓扑排序序列的步骤 ：

   • (1) 从DAG图中选择一个没有前驱(入度为0)的顶点输出
   • (2) 删除(1)中的顶点，并删除以它为起点的所有有向边
   • (3) 重复上述(1)(2)直至当前DAG为空或当前图中不存在无前驱的顶点为止

代码实现

1. 选取入度为0的顶点输出
2. 统计输出顶点的计数器count，看排序是否成功
   count < 图的顶点数，则有环路
   count = 图的顶点数，拓扑排序成功

图G的拓扑排序代码实现 ：