下载此文档

7.5 有向无环图和应用.ppt


文档分类:幼儿/小学教育 | 页数:约20页 举报非法文档有奖
1/20
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/20 下载此文档
文档列表 文档介绍
拓扑排序——用顶点边表示活动的网络,简称AOV网络(ActivityOnVertices)顶点:一个工程中的活动(Activity)边:活动的顶点间的优先关系(Relation)要解决的问题是:将各个顶点(代表各个活动)排列成一个线性有序的序列,使得AOV网络中所有应存在的前驱和后继关系都能得到满足。课程代号课程名先修课程C1高等数学C2程序设计基础C3离散数学C1,C2C4数据结构C3,C2C5高级语言程序设计C2C6编译方法C5,C4C7操作系统C4,C9C8普通物理C1C9计算机原理C8可以用有向图表示一个工程。在这种有向图中,用顶点表示活动。有向边<Vi,Vj>表示:Vi必须先于活动Vj进行。这种有向图叫做顶点表示活动的AOV网络(ActivityOnVertices)。在AOV网络中,如果活动Vi必须在活动Vj之前进行,则存在有向边<Vi,Vj>,AOV网络中不能出现有向回路,即有向环。在AOV网络中如果出现了有向环,则意味着某项活动应以自己作为先决条件。因此,对给定的AOV网络,必须先判断它是否存在有向环。一、什么是拓扑排序将各个顶点(代表各个活动)排列成一个线性有序的序列,使得AOV网络中所有应存在的前驱和后继关系都能得到满足。这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。例如,对学生选课工程图进行拓扑排序,得到的拓扑有序序列为C1,C2,C3,C4,C5,C6,C8,C9,C7 或C1,C8,C9,C2,C5,C3,C4,C7,C6例如,对学生选课工程图进行拓扑排序,得到的拓扑有序序列为C1,C2,C3,C4,C5,C6,C8,C9,C7 或C1,C8,C9,C2,C5,C3,C4,C7,C6二、进行拓扑排序的方法首先建立(n个顶点的)AOV网。(1)在AOV网络中选一个没有直接前驱的顶点(入度为0的顶点),并输出之;(2)从图中删去该顶点,同时删去所有它发出的边;重复(1)和(2),直到全部顶点均已输出,拓扑有序序列形成,拓扑排序完成;若图中还有未输出的顶点,但已跳出处理循环。这说明图中存在环。v1v5v4v3v6三、拓扑排序的过程有向无环图v2v1v5v4v3v6v2(1)输出顶点v6(2)输出顶点v1(3)输出顶点v3(4)输出顶点v4(5)输出顶点v2(6)输出顶点v5四、存储结构(邻接表)v1v2v3v4v5v612345602123043552054idvexfirstdataarcv1v5v4v3v6v22adjvexnextarc

7.5 有向无环图和应用 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数20
  • 收藏数0 收藏
  • 顶次数0
  • 上传人85872037
  • 文件大小188 KB
  • 时间2020-04-03