Tag Archives: 拓扑排序

数据结构重读 - AOV网和关键路径

与AOV网对应的，还有一个AOE网，当然它也是有DAG(向无环图)。

AOE(Activity On Edge)网：顾名思义，用边表示活动的网。

与AOV不同，活动都表示在了边上，如下图所示：

如上所示，共有11项活动（11条边），9个事件（9个顶点）。

整个工程只有一个开始点和一个完成点。

即只有一个入度为零的点（源点）和只有一个出度为零的点（汇点）。

(1) 关键路径：是从开始点到完成点的最长路径的长度。路径的长度是边上活动耗费的时间。

(2[......]

数据结构重读 - 有向无环图、AOV网和拓扑排序

DAG和概念
有向无环图：顾名思义，有向图，且不含环，directed acycline graph，简称DAG图。

无向图检查环：若深度优先遍历过程遇到回边（先前访问过的顶点的边），则必定存在环。

有向图检查环：从某个顶点v出发，在dfs(v)结束前，出现一条从顶点u到顶点v的回边，由于u在生成树上是v的子孙，则有向图必定存在包含顶点v和u之间的环。

DAG图是描述工程的有效工具。一个工程可以用一个DAG图表示，每一个顶点是一个子工程，工程的先后关系用弧表示。

围绕着[......]