有向无环图的应用—AOV网 和 拓扑排序

有向无环图:无环的有向图,简称 DAG (Directed Acycline Graph) 图。

一个有向图的生成树是一个有向树,一个非连通有向图的若干强连通分量生成若干有向树,这些有向数形成生成森林。

在工程计划和管理方面的应用

除最简单的情况之外,几乎所有的工程都可分为若干个称作“活动”的子工程,并且这些子工程之间通常受着一定条件的约束,例如:其中某些子工程必须在另一些子工

程完成之后才能开始。对整个工程和系统,人们关心的是两方面的问题:

一是工程能否顺利进行,即工程流程是否“合理”;

二是完成整个工程所必须的最短时间。

对应到有向图即为进行拓扑排序(AOV网)和求关键路径(AOE网)。 

拓扑排序

AOV 网:用一个有向图表示一个工程的各子工程及其相互制约的关系,其中以顶点表示活动,弧表示活动之间的优先制约关系,称这种有向图为顶点表示活动的网,简称AOV (Activity On  Vertex network)网。

比如、某工程可分为7个子工程(V0、V1、V2、V3、V4、V5、V6),若用顶点表示子工程(也称活动),用弧表示子工程间的顺序关系,工程流程可用如下的AOV网表示。

比如排课表

AOV 网的特点:若从 i 到 j 有一条有向路径,则 i是 j 的前驱;j 是 i 的后继。若 < i , j > 是网中有向边,则 i 是 j 的直接前驱; j 是 i 的直接后继。AOV 网中不允许有回路,因为如果有回路存在,则表明某项活动以自己为先决条件,显然这是荒谬的。

问题:如何判别 AOV 网中是否存在回路?即如何AOV网表示的工程能顺利进行?合理?

拓扑排序:

在 AOV 网没有回路的前提下,我们将全部活动排列成一个线性序,使得若 AOV 网中有弧 <i,  j> 存在,则在这个序列中, i  一定排在  j的前面,具有这种性质的线性序列称为拓扑有序序列,相应的拓扑有序排序的算法称为拓扑排序。

注意:

1、若将图中顶点按拓扑次序排成一行,则图中所有的有向边均是从左指向右的。

2、若图中存在有向环,则不可能使顶点满足拓扑次序。

3、一个DAG可能存在多个拓扑序列。

检测 AOV 网中是否存在环方法:

DFS(深度优先搜索),出现返回边则有环;拓扑排序,若所有的顶点都出现在拓扑排序中,则不出现环。如果使用 DFS 进行拓扑排序,那么结果是逆向的拓扑排序有序序列。 

拓扑排序方法:

1)在有向图中选一个无前趋的顶点v,输出之;

2)从有向图中删除v及以v为尾的弧;

3)重复1)、2),直接全部输出全部顶点或有向图中不存在无前趋的结点时为止。

删除 v2,v3,v4,v5,v6以及以他们为尾部的弧 

注意:一个AOV网的拓扑序列不是唯一的

 

辛苦的劳动,转载请注明出处,谢谢……

http://www.cnblogs.com/kubixuesheng/p/4404004.html

时间: 2024-10-28 21:19:10

有向无环图的应用—AOV网 和 拓扑排序的相关文章

算法研究:AOV网与拓扑排序

在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我 们称之为AOV网(Activity on Vextex Network).AOV网中的弧表示活动之间存在的某种制约关系,AOV网中不能存在回路, 让某个活动的开始要以自己完成作为先决条件,显然是不可以的. 设G= { V, E }是一个具有n个顶点的有向图,V中 的顶点序列v1, v2, ...,vn,满足若从顶点vi到vj有一条路径,则在顶点序列中顶点vi必在vj之前,则我们称这样的顶点

如何高效地计算出一个有向无环图中各个节点的祖先节点数和后代节点数?

问题描述 如何高效地计算出一个有向无环图中各个节点的祖先节点数和后代节点数? 数据量较大,希望复杂度尽量低.现在实现图的数据结构是用HashMap记录对应标号的节点,再分别对每个节点使用HashMap记录子节点.感谢!

AOV网络及拓扑排序

/* AOV网络及拓扑排序 1.在有向无环图中,用顶点表示活动,用有向边<u,v>表示活动u必须先与活动v,这种有向图叫AOV网络. 2.若<u,v>,则u是v的直接前驱,v是u的直接后继:若<u,u1,u2,···un,v>则称u是v的前驱,v是u的后继. 3.前驱后继关系有传递性和反自反性.则可以推断AOV网络必须是有向无环图. 4.拓扑排序实现方法: 1)从AOV网络中选择一个入度为0的顶点并输出: 2)从AOV网络中删除该顶点以及该顶点发出的所有边: 3)重复1

判断给定的图是不是有向无环图实例代码_C 语言

复制代码 代码如下: #include<iostream>#include<list>#include<stack>using namespace std; class Graph { int vertexNum; list<int> *adjacents;public: Graph(int _vertexNum) {  vertexNum = _vertexNum;  adjacents = new list<int>[vertexNum]; 

图的遍历、拓扑排序、最短路径算法

1.DFS(深度优先搜索) 深度优先搜索算法(Depth-First-Search),是搜索算法的一种.它沿着树的深度遍历树的节点,尽可能深的搜索树的分支.当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点.这一过程一直进行到已发现从源节点可达的所有节点为止.如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止.DFS 属于盲目搜索. 深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标图的相应拓扑排序表,利用

iis8-IIS8无法本机浏览而内网其它机器正常

问题描述 IIS8无法本机浏览而内网其它机器正常 Windows sever 2012 R2中的IIS8,网站启用后,在本机无法用浏览器浏览,显示无法显示此页,但在局域网内的其它机器可以正常浏览 解决方案 你检查一下本机浏览的地址是否跟局域网其它机器浏览地址是否一致?怀疑你地址录入错误

吕方获封“殿堂级歌手”称与郑裕玲无联系(图)

获薛家燕和朱明锐颁发"劲爆殿堂歌手"奖,吕方有点意外 新浪娱乐讯 北京时间12月24日消息,据香港媒体报道,吕方昨天到新城电台接受薛家燕主持的<粤港越优游>节目访问,并获颁发"新城劲爆殿堂歌手"奖.这个奖是吕方近年来的首次,因此感到有些意外.问及即将推出的新碟有否赠给前度女友郑裕玲,吕方称二人已不再联系. 吕方将于明年1月14日推出新曲加精选碟,3月会举行个唱,问到会否把新碟赠给前度女友郑裕玲?他说:"不会啦,如果是朋友都会自己买.(嘟嘟最近开

关键路径:php实现图的邻接表,关键路径,拓朴排序

<?php//调用require 'algraph.php';$a = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j');$e = array('ab'=>'3', 'ac'=>'4', 'be'=>'6', 'bd'=>'5', 'cd'=>'8', 'cf'=>'7', 'de'=>'3', 'eg'=>'9', 'eh'=>'4', 'fh'=>'6', 'gj'=>

无百度时代,淘宝网如何生存?

近日,淘宝网站屏蔽百度搜索爬虫,禁止百度搜索引擎抓取淘宝网站.这无疑会使广大淘宝店的流量受到影响.流量是淘宝店提升销售量的门槛,没有流量,就象没有人光顾你的店铺,怎么还有钱可赚?因此,"无百度时代"的淘宝店,当务之急,是如何提升店铺的流量.与阿里妈妈合作是一个方面,主动与广大中小网站,尤其是垂直网站合作,也是务实之举. 首先,什么是垂直网站?所谓垂直网站,是与大而全的水平网站(又称综合性网站)相区别的.垂直网站注意力集中在某些特定的领域或某种特定的需求,提供有关这个领域或需求的全部深度