AOV与AOE

AOV与AOE

编程基础 • 2024-12-18 07:57 • 阅读 52

1.AOV（拓扑排序）
1. AOV的概念：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称AOV网
2.拓扑排序：按照有向图给出的次序关系，将图中的顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系，由此所得顶点的线性序列称为拓扑有序序列。
基本思路。
从AOV网中选择一个没有前驱的顶点并且输出；//入度in不为零
从AOV网中删去该顶点，并且删去所有以该顶点为尾的弧；
重复上述两步，直到全部顶点都被输出，或AOV网中不存在没有前驱的顶点。

1.AOE的概念：
在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的持续时间，称这样的有向图叫做边表示活动的网，简称AOE网。
AOE网中没有入边的顶点称为始点（或源点），没有出边的顶点称为终点（或汇点）。
2.AOE的性质：
只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始；
只有在进入某顶点的各活动都结束，该顶点所代表的事情才可以发生
关键路径。
从始点到终点的路径可能不止一条，只有各条路径上所有活动都完成了，整个工程才算完成。
因此，完成整个工程所需的最短时间取决于从始点到终点的最长路径长度，即这条路径上所有活动的持续时间之和。
这条路径长度最长的路径就叫做关键路径。
要找出关键路径，必须找出关键活动, 即不按期完成就会影响整个工程完成的活动

关键活动。
事件的最早发生时间ve[k] ve[k]=max{ve[j]+len<vj, vk>}（指从始点开始到顶点vk的最大路径长度）
事件的最迟发生时间vl[k] vl[k]=min{vl[j]-len<vk , vj>}（不推迟整个工期的前提下,事件vk允许的最晚发生时间。）
活动的最早开始时间e[i]
活动的最晚开始时间l[i]
最后计算各个活动的时间余量 l[k] - e[k]，时间余量为0者即为关键活动

具体代码这就不给出了，期末复习时再多多探讨。

今天的文章 AOV与AOE分享到此就结束了，感谢您的阅读。

相关推荐