《图有向无环图》PPT课件

《《图有向无环图》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、7.5有向无环图及其应用1、何为有向无环图（DAG图）实例BEFGLFGBEFGLFGBEFGLFG有向树DAG图有向图（含环）用途：描述工程项目或系统进行的工具AOV网络：定义结点为活动，有向边的指向表示活动执行的次序。AOE网络：定义结点为事件，有向边的指向表示事件的执行次序。单位是时间（时刻）。有向边定义为活动，它的权值定义为活动进行所需要的时间。ABAB102、拓扑排序（TopologicalSort）偏序：若集合X上的关系R是传递的、自反的、反对称的，则称R是集合X上的偏序关系。全序：若关系R是集合X上的偏序关系，

2、如果对于每个x,y属于X，必有xRy或yRx，则称R是集合X上的全序关系。复习：拓扑排序：如果有一个序列A=a1,a2,a3…………an是集合X上的元素的一个序列，且当i

3、向表示活动执行的次序。实例：下述集合M代表课程的集合，其中，1代表数学，2代表程序设计，3代表离散数学，4代表汇编程序设计，5代表数据结构，6代表结构程序设计,7代表编译原理。关系R课程学习的先后关系，如数学必须在离散数学之前学习。要求排一张学习的先后次序表。1327564第一个输出的结点：必须无前件。后件：必须等到它的前件输出之后输出。无前件及后件的结点：任何时候都可输出。序列：1、3、2、4、6、5、7合乎拓扑排序的要求序号1、2、3、4、5、6、7合乎拓扑排序的要求序列：3、1、2、4、6、5、7不合乎拓扑排序的要求元

4、素3的序号1（后件）<元素1（前件）的序号2132756413246571327564可交换可交换可交换算法（使用邻接矩阵）：1327564011000000001110000101000000000000010000001000000012345671234567算法的执行步骤：1、找到全为零的第j列，输出j2、将第j行的全部元素置为零3、找到全为零的第k列，输出k4、将第k行的全部元素置为零…………………反复执行3、4；直至所有元素输出完毕。0000000000011100001010000000000000100000

5、010000000算法（使用邻接表）：1327564算法的执行步骤：1、用一个数组记录每个结点的入度。将入度为零的结点进栈。2、将栈中入度为零的结点V输出。3、根据邻接表找到结点V的所有的邻接结点，并将这些邻接结点的入度减一。如果某一结点的入度变为零，则进栈。4、反复执行2、3；直至栈空为止。…………………次序执行结束，如果输出结点数等于图的结点总数，则有向图有环，否则有向图有环。12120123456null34463455nullnullnull6763nullnullnullnull01012345611213inde

6、gree0栈1327564算法（使用邻接表）：StatusTopologicalsort（ALGraphG）{findinDegree（G，indegree）;Initstack（S）；for（i=0;inextarc）;{k=p

7、->adjnexr;if（!（--indegree[k]））Push（S,k）;}}if（count

8、件先发生，而终止结点事件才能发生。B10A关键活动：最早开始时间＝最迟开始时间的活动关键路径：从源点到汇点的最长的一条路径，或者全部由关键活动构成的路径。kjdut(j,k)ai术语：事件的最早发生时间（Ve(j)）：从起点到本结点的最长的路径。意味着事件最早能够发生的时刻。事件的最迟发生