一些概念
-
有向无环图 ： 一个有向图中不存在环，则称为有向无环图，简称
DAG -
AOV （Activity on Vertex） ：活动在
顶点上的网，是一种可形象反映出整个工程中各个活动之间的先后关系的`有向无环图。
例如： 制作一个产品的AOV网
AOV网
AOE （Activity on Edge）：活动在
边上的网
对于一个表工程的AOE网，只存在一个入度为0的顶点，称为源点，表示工程的开始；
也只有一个出度为0的顶点，称为汇点，表示整个工程的结束。总结
| AOV | AOE |
|---|---|
有向无环图DAG
|
有向无环图DAG
|
| 顶点表示活动；边无权值；边代表活动之间的先后顺序 | 边表示活动；边有权值；边的权值代表活动的持续时间；顶点表示事件；事件是图中新活动开始或者旧事件结束的标志 |
拓扑排序
-
概念：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，该序列称为该图的一个拓扑排序
- (1) 每个顶点出现且只出现一次
- (2) 若
A在序列中排在B的前面，则在图中不存在B->A的路径
对一个
DAG进行拓扑排序，是将图G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若存在u到v的路径，则在拓扑排序中一定是u出现在v的前边每一个DAG图都有一个或多个拓扑排序序列
-
DAG中找到一个拓扑排序序列的步骤 ：
- (1) 从DAG图中选择一个没有前驱(
入度为0)的顶点输出 - (2) 删除
(1)中的顶点，并删除以它为起点的所有有向边 - (3) 重复上述
(1)(2)直至当前DAG为空或当前图中不存在无前驱的顶点为止
- (1) 从DAG图中选择一个没有前驱(
代码实现
- 选取入度为0的顶点输出
- 统计输出顶点的计数器count，看排序是否成功
count < 图的顶点数，则有环路
count = 图的顶点数，拓扑排序成功
图G的拓扑排序代码实现 ：
