数据结构 罗吴蔓 电子科大 ppt 考研chapt7#39;.pptVIP

第七章 图 7.1 图的定义和术语 二. 图的基本操作 “顶点在图中的位置”: 对图中顶点进行人为任意排列, 顶点在这个排列中的位置(或序号)。 “邻接点的位置”: 对某个顶点的邻接点也可进行人为任意排列, 邻接点在这个排列中的序号。 7.1 图的定义和术语 LOC_VERTEX(G,v) 顶点定位函数 GET_VERTEX(G,i) 取顶点函数 FIRST_ADJ(G,v) 求第一个邻接点函数 NEXT_ADJ(G,v,w) 求下一个邻接点函数 二、拓扑排序算法 算法步骤 (1) 在AOV网中，选取一个没有前驱的顶点输出； (2) 删除该顶点和所有以它为弧尾的弧； (3) 重复以上两步，直到 AOV网中全部顶点都已输出（得到拓扑有序序列） 或者，图中再无没有前驱的顶点（AOV网中有环） 二、拓扑排序算法 如何实现算法中的(1)和(2)？ 对于(1)，没有前驱的顶点即入度为0的顶点； 对于(2)，删除以它为弧尾的所有弧，即让该顶点的所有直接后继的入度减1。 7.6 关键路径 一、AOE网（activity on edge） 若有向图中，顶点表示事件，弧表示活动，弧上的权表示完成该活动所需的时间，则称这类有向图为边表示活动的网（AOE网） AOE网中仅有一个入度为0的事件，称为源点，它表示工程的开始；网中也仅有一个出度为0的事件，称为汇点，它表示工程的结束。 每一事件V表示以它为弧头的所有活动已经完成，同时，也表示以它为弧尾的所有活动可以开始。 7.6 关键路径 AOE网可解决如下问题： 估算工程的最短工期（从源点到 汇点至少需要多少时间） 找出哪些活动是影响整个工程进展的关键 7.6 关键路径 二、几个术语 路径长度：路径上各活动持续时间的总和 （即：路径上所有弧的权值之和） 关键路径：从源点到汇点之间路径长度最长的路径 （不一定唯一） 事件V i的最早发生时间ve(i)：从源点到V i的最长路径长度 活动 ai的最早开始时间e(i)：等于该活动的弧尾事件V j的最早发生时间 即若j, k表示活动ai ，则有e(i)=ve(j) 7.6 关键路径 事件 vk 的最迟发生时间 vl(k)：是在不推迟整个工期的前提下，该事件最迟必须发生的时间 活动ai的最迟开始时间L(i)：是该活动的弧头事件的最迟发生时间与该活动的持续时间之差， 即L(i)=vl(k)- ai 的持续时间 关键活动：l(i)=e(i)的活动 7.6 关键路径 三、关键路径算法思想 1. 从ve(1)=0 开始利用下面递推公式，计算出各事件的最早发生时间 ve(j)=Max{ve(i)+dut(i, j)}， j=2, …… , n ， i, j ∈T 其中：T是所有以j为头的弧集合， dut(i,j)表示活动的持续时间 前例中，ve(5)=Max{ve(2)+dut(2,5)， ve(3)+dut(3,5)} =Max{6+1,4+1}=7 7.6 关键路径 2. 从vl(n)=ve(n)开始，利用下面递推公式，计算出各事件的最迟发生时间： vl(i)=Min{vl(j)-dut(i, j)} i=n-1 , …… , 2 , 1 , i, j ∈S 其中：S是所有以i为尾的弧集合 7.6 关键路径 3. 设活动ai由弧j, k表示，其持续时间为dut(j,k)，则利用下面公式，计算出各活动的最早、最迟开始时间： e(i)=ve(j) l(i)=vl(k)-dut(j,k) 4. 找出e(i)=l(i)的活动，即为关键活动，诸关键活动组成的从源点到汇点的路径即为关键路径 7.6 关键路径 四、例子 7.6 关键路径 关键路径上的活动都是关键活动。 缩短非关键活动都不能缩短整个工期 如a6缩短为1，则整个工期仍为8。 又如a6推迟3天开始，或拖延3天完成 （a6=6）均不影响整个工期 分析关键路径的目的是找出影响整个工期的关键活动，缩短关键活动的持续时间，常可以缩短整个工期。 如a7缩短为1，则整个工期为7。 此时，再缩短任一关键活动均不能缩短整个工期。 即在有多条关键路径时，缩短那些在所有关键路上的关键活动，才能缩短整个工期 7.6 关键路径 7.7 最短路径在有向图中，寻找从某个源点到其余各个顶点或者每一对顶点之间的最短带权路径的运算，称为最短路径问