当前位置:   article > 正文

AOV网和AOE网

在aov网中 弧的权值

1、AOV网

定义:在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们成为AOV网(Activity On Vertex Network),AOV网中的弧表示活动之间的某种约束关系。AOV网中不存在回路(即无环的有向图)。

拓扑排序

定义:设G(V,E)是一个具有n个顶点的有向图,V中的顶点序列v1,v2,.....,vn,满足若从顶点vi到vj有一条路径,则顶点vi必在vj之前。这样的顶点序列成为拓扑序列。

拓扑排序其实就是对一个有向图构造拓扑序列的过程。

对AOV网进行拓扑排序的基本思路是:从AOV网中选择一个入度为0的顶点输出,然后从有向图中删除该定点,并删除以此顶点为尾的弧,继续重复此步骤,直到输出全部顶点或AOV网中不存在入度为0的顶点为止。

拓扑排序使用邻接表的数据结构。还用栈作为辅助数据结构,用来存储处理过程中入度为0的顶点,目的是为了避免每次查找时都要去遍历邻接表找有没有入度为0的顶点。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/笔触狂放9/article/detail/258303
推荐阅读
相关标签
  

闽ICP备14008679号