网和aoe网的区别_AOV、AOE网络求解诀窍大公开，你看不懂算我输！-程序员宅基地

说到数据结构当中的图这一章节，除了图的基本概念、基本性质和几个看似复杂但是实际比较简单的算法(例如最小生成树、最短路径等)之外，最最让大家头疼的就是AOV网络和AOE网路了，不少学校将求解AOV、AOE的计算题或者画图简单题当作数据结构的压轴题目，这两个结构的求解算法也不像图章节中的其他问题那么简单。

今天

大牛学长就用一篇文章的篇幅

教大家搞定AOV、AOE这一对难题。

一、AOV网络

1、 AOV网络的定义

AOV网络(Activity On Vertex Network)：若用有向无环图(DAG) 表示一个工程，而图中的顶点表示活动，用有向边＜，＞表示活动必须先于活动的这样一种关系，则将这种有向图称为顶点表示活动的网络，记为AOV网。在AOV网络中，活动是活动的直接前驱，活动是活动的直接后继，如下图1所示为一个简单的AOV网络。

2、 AOV网络拓扑排序算法

(a) 算法步骤：

① AOV 网中选择一个没有前驱的顶点并输出

② 从网络中删除该顶点和所有以它为起点的有向边。

③ 重复上面两个步骤，直到当前的AOV网络为空或当前网络中不存在无前驱的顶点为止。

(b) 算法图解

对图1中的AOV网络进行拓扑排序：

① 选中无前驱节点的1号活动节点，输出该节点；

② 把网中该输出节点的出边都删除；

重复上述两个步骤，则可以得到AOV网络的拓扑序列为1，2，4，3，5，

备注：用拓扑排序算法处理 AOV 网时，应注意以下问题：

① 入度为零的顶点，工程可以从这个顶点所代表的活动开始或继续；

② 若一个顶点有多个直接后继，则拓扑排序的结果通常不唯一；

③ AOV 网中各顶点的地位平等，每个顶点编号是人为的。

二、AOE网络

1、 AOE网络的定义

AOE网络(Activity On Edge Network)：在带权有向图中，顶点表示事件，有向边表示活动，而边上的权值表示完成该活动的开销(完成活动所需的时间)，则把该类图称之为用边表示活动的网络，简称AOE网络，如图2所示，顶点表示事件，边表示对应的活动。

2、AOE网络的性质

① 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；

② 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。

3、 AOE网络之应用——关键路径

(a)关键路径：指从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。完成整个工程的最短时间就是关键路径的长度，即关键路径上各活动花费开销的总和。

(b)寻找关键路径需要明确的几个参量

① 事件发生的最早时间ve(k)(从源点开始计算)：它是指从源点到顶点的最长路径长度，计算公式如下：

ve(源点)=0；

ve(k)=Max{ve(j) + Weight(，)}, 为的任意后继，Weight(，)表示，事件相连的权值。

② 事件发生的最迟时间vl(k)(从汇点开始计算)：它是指在不推迟整个工程完成的前提下，即保证它的后继事件在其最迟发生时间vl(j)能够发生时，该事件最迟必须发生的时间，计算公式如下：

vl(汇点)=ve(汇点)；

vl(k)=Min{vl(j) - Weight(，)}, 为的任意后继，Weight(，)表示，事件相连的权值。

③ 活动的最早开始时间e(i):若边＜, >表示活动，则有e(i) =ve(k)，即活动的最早开始时间e(i)为该活动弧的起点所表示事件的最早发生时间。

④ 活动的最早开始时间l(i): 若边＜, >表示活动，则有l(i) = vl(j) - Weight(，)，它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。

⑤ 计算d(i)=l(i)-e(i)，该变量是指该活动完成的时间余量，即在不增加完成整个工程所需总时间的情况下，活动可以拖延的时间，若d(i)=0,则表示这个活动不能拖延，我们把该活动称为关键活动。

(c)AOE网络中求关键路径的算法步骤：

1) 从源点出发，令ve(源点)= 0，按拓扑序列求其余顶点的最早发生时间 ve()。

2) 从汇点出友，令 vi(汇点)= ve(汇点)，按逆拓扑序列求其余顶点的最迟发生时间vl()。

3) 根据各顶点的ve()值求所有活动的最早开始时间e()。

4) 根据各顶点的 vl()值求所有活动的最迟开始时间l()。

5) 求 AOE 网中所有活动的差额d()，找出所有 d()= 0的活动构成关键路径。

根据上述求AOE网络关键路径的算法，可以计算图2的关键路径如下图所示：

三、AOV网络与AOE网络区别与联系

AOE 网络和AOV网络都是有向无环图，不同之处在于它们的边和顶点所代表的含义是不同的，AOV网络中的活动以顶点表示，而AOE网络中的活动以有向边来表示，AOV网的有向边只表示活动的先后次序，然而AOE网络中的边有权值；而AOV网络中的边无权值，仅表示顶点之间的前后关系。

—the end—

今天是2020年 8 月 26 日

距离2021考研还有 114 天

苦尽甘来终有时，山河星月代贺礼。

大牛学长一直在~

本文链接：https://blog.csdn.net/weixin_39713538/article/details/112701285

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

c# 调用c++ lib静态库_c#调用lib-程序员宅基地

文章浏览阅读2w次，点赞7次，收藏51次。四个步骤1.创建C++ Win32项目动态库dll 2.在Win32项目动态库中添加外部依赖项 lib头文件和lib库3.导出C接口4.c#调用c++动态库开始你的表演...①创建一个空白的解决方案，在解决方案中添加 Visual C++ , Win32 项目空白解决方案的创建：添加Visual C++ , Win32 项目这......_c#调用lib

deepin/ubuntu安装苹方字体-程序员宅基地

文章浏览阅读4.6k次。苹方字体是苹果系统上的黑体，挺好看的。注重颜值的网站都会使用，例如知乎：font-family: -apple-system, BlinkMacSystemFont, Helvetica Neue, PingFang SC, Microsoft YaHei, Source Han Sans SC, Noto Sans CJK SC, W..._ubuntu pingfang

html表单常见操作汇总_html表单的处理程序有那些-程序员宅基地

文章浏览阅读159次。表单表单概述表单标签表单域按钮控件demo表单标签表单标签基本语法结构<form action="处理数据程序的url地址“ method=”get|post“ name="表单名称”></form><!--method将表单中的数据传送给服务器处理，get方式直接显示在url地址中，数据可以被缓存，且长度有限制；而post方式数据隐藏传输，_html表单的处理程序有那些

PHP设置谷歌验证器（Google Authenticator）实现操作二步验证_php otp 验证器-程序员宅基地

文章浏览阅读1.2k次。使用说明:开启Google的登陆二步验证（即Google Authenticator服务）后用户登陆时需要输入额外由手机客户端生成的一次性密码。实现Google Authenticator功能需要服务器端和客户端的支持。服务器端负责密钥的生成、验证一次性密码是否正确。客户端记录密钥后生成一次性密码。下载谷歌验证类库文件放到项目合适位置(我这边放在项目Vender下面)https://github.com/PHPGangsta/GoogleAuthenticatorPHP代码示例://引入谷_php otp 验证器

【Python】matplotlib.plot画图横坐标混乱及间隔处理_matplotlib更改横轴间距-程序员宅基地

文章浏览阅读4.3k次，点赞5次，收藏11次。matplotlib.plot画图横坐标混乱及间隔处理_matplotlib更改横轴间距

docker — 容器存储_docker 保存容器-程序员宅基地

文章浏览阅读2.2k次。①Storage driver 处理各镜像层及容器层的处理细节，实现了多层数据的堆叠，为用户提供了多层数据合并后的统一视图②所有 Storage driver 都使用可堆叠图像层和写时复制（CoW）策略③docker info 命令可查看当系统上的 storage driver主要用于测试目的，不建议用于生成环境。_docker 保存容器

随便推点

网络拓扑结构_网络拓扑csdn-程序员宅基地

文章浏览阅读834次，点赞27次，收藏13次。网络拓扑结构是指计算机网络中各组件（如计算机、服务器、打印机、路由器、交换机等设备）及其连接线路在物理布局或逻辑构型上的排列形式。这种布局不仅描述了设备间的实际物理连接方式，也决定了数据在网络中流动的路径和方式。不同的网络拓扑结构影响着网络的性能、可靠性、可扩展性及管理维护的难易程度。_网络拓扑csdn

JS重写Date函数，兼容IOS系统_date.prototype 将所有 ios-程序员宅基地

文章浏览阅读1.8k次，点赞5次，收藏8次。IOS系统Date的坑要创建一个指定时间的new Date对象时，通常的做法是：new Date("2020-09-21 11:11:00")这行代码在 PC 端和安卓端都是正常的，而在 iOS 端则会提示 Invalid Date 无效日期。在IOS年月日中间的横岗许换成斜杠，也就是new Date("2020/09/21 11:11:00")通常为了兼容IOS的这个坑，需要做一些额外的特殊处理，笔者在开发的时候经常会忘了兼容IOS系统。所以就想试着重写Date函数，一劳永逸，避免每次ne_date.prototype 将所有 ios