美文网首页
图之--AOV/AOE网及关键路径

图之--AOV/AOE网及关键路径

作者: 美雨知春 | 来源:发表于2020-10-08 22:36 被阅读0次

有向图的两个广泛应用的网络,AOV和AOE网
AOV网:图中的顶点表示活动,边表示依赖关系
AOE网:图中的顶点表示事件,边表示事件持续的时间,20世纪40年代美国军方研发

  1. AOV网
    举个例子就很容易解释:比如大学里的选课系统,大学物理要在完成高等数学之后才能学习
    这里有个死循环的问题,如果两个科目互相依赖就是死循环。存在死循环的网络是AOV网但不是拓扑序列。
    拓扑排序算法:
    1)从N中选出一个入度为0的顶点作为序列的下一个顶点
    2)从N网中删除所选顶点及所有的出边
    3)循环1)-2)直到再也没有入度为0的顶点时算法结束
    涉及关键技术:零度表的建立
    连通图时间复杂度:O(E+V),空间复杂度:O(v)
    链接矩阵的时间复杂度:O(V2)
  2. AOE网和关键路径
    AOE网是无环的带权有向图。关键路径是找出图中从起点到终点的最慢的时间路径。完成整个工程所需要的最少的时间取决于这条路径,所以称之为关键路径。

相关文章

  • 图之--AOV/AOE网及关键路径

    有向图的两个广泛应用的网络,AOV和AOE网AOV网:图中的顶点表示活动,边表示依赖关系AOE网:图中的顶点表示事...

  • 数据结构 图之关键路径

    关键路径 网络 AOV网络:有向图,用顶点表示活动,用弧表示活动的先后顺序AOE网络:有向图,用顶点表示事件,用弧...

  • 图-关键路径(AOE网)

    AOE网:在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,用边上的权值表示活动的持续时间,这种有向...

  • AOV网与AOE网

    AOV网: 顶点表示活动,有向边表示课程的先导关系。 AOV网是有向无环图,即不应该带有回路,因为若带有回路,则会...

  • 图的关键路径

    关键路径:在AOV网中,路径上各个活动所持续的时间之和称为路径长度,从源点到汇点具有最大长度的路径叫做关键路径。 ...

  • 5.7 关键路径

    在拓扑排序的AOV图基础上,给每条边加上权重AOV图就成了AOE图了。同样是描述工程或者一个过程的关于活动的图。 ...

  • 关键路径算法演示(AOE网)

    如上图,是一个AOE网,点表示状态,边表示活动及其所需要的时间。为了求出关键路径,我们使用一下算法: 1.求出到达...

  • [图] AOE网络与关键路径

    详细内容见:http://www.cnblogs.com/KennyRom/p/6135849.html

  • 数据结构第二季 Day09 图 拓扑排序、最小生成树、prim算

    一、 拓扑排序(TopologicalSort) 1、一句话概括什么是 AOV 网?AOV 网必须是有向无环图吗?...

  • AOE关键路径算法及代码(C++版)

    起因我上网搜了很久,没有看见别人写的AOE算法,要么就是用C写的,看上去很复杂,也没搞清楚他们这样写的意义。又看到...

网友评论

      本文标题:图之--AOV/AOE网及关键路径

      本文链接:https://www.haomeiwen.com/subject/xzqkpktx.html