数据结构与算法 (33).pdf

《数据结构与算法 (33).pdf》由会员分享，可在线阅读，更多相关《数据结构与算法 (33).pdf（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、10.1 图的概念10.2 图的存储10.3 图的遍历10.4 生成树和最小生成树10.5 最短路径 10.6 有向无环图的应用第10章图及其应用 10.6.1 拓扑排序10.6.2 关键路径10.6 有向无环图的应用3 问题提出问题提出一个无环的有向图称作有向无环图，简称DAG图。DAG图在工程计划和管理方面应用广泛。几乎所有的工程(project)都可分为若干个称作“活动”的子工程，并且这些子工程之间通常受着一定条件的约束。4某些子工程必须在另外的一些子工程完成之后才能开始。对整个工程和系统，人们主要关心的是两方面的问题：（1）工程能否顺利进行；（2）完成整个工程所必须的最短时间。问题提出

2、问题提出拓扑排序关键路径5计算机专业课程次序的安排就是一个简单的工程，每一门课程的学习都是整个工程的活动。其中有些课程要求先安排，有些则不需要，如何安排好课程学习的先后次序，这是一个典型的拓扑排序问题。拓扑排序示例分析6课程编号课程名称先修课程C1高等数学无C2程序设计基础无C3离散数学C1,C2C4数据结构C2,C3C5算法语言C2C6编译技术C4,C5C7操作系统C4,C9C8普通物理C1C9计算机原理C8 拓扑排序示例分析有先修课程的须按先后关系开设7C2C1C8C9C3C4C5C6C7其中,顶点表示课程,有向边表示前提条件。若课程vi为课程vj的先行课,则必然存在有向边 vi,vj。生

3、成DAG图8AOV网(Activity On Vertex Network)：将顶点表示活动，边表示活动之间的关系的网称为顶点活动网。拓扑序列：把AOV网中的所有顶点排成一个线性序列，该序列满足如下条件：若AOV网中存在从vi到vj的路径，则在该序列中，vi必位于vj之前。拓扑排序有关概念拓扑排序：构造AOV网的拓扑序列的过程被称为拓扑排序。9(1)一个有向图的拓扑序列不一定唯一;(2)有向无环图一定存在拓扑序列;(3)有向有环图不存在拓扑序列;(4)通过构造拓扑序列，可判定AOV网是否存在环。拓扑排序特点10 拓扑排序算法的基本思想(1)在有向图中选一个入度为0的顶点输出。(2)从图中删除该

4、顶点及所有它的出边。(3)重复执行（1）和（2），直到全部顶点均已输出，或图中剩余顶点的入度均不为0(说明图中存在回路，无法继续拓扑排序)。11123897564123897564 拓扑排序算法的示例演示讨论：如果顶点还没有输出完而找不到入度为零的顶点怎么办？答案：存在环路，无法进行拓扑排序，退出。121234564355adjvexnextarc2524datafirstarc134256例1345255v1v2 V3V4V5 V6342021230indegree栈v1v6v4v32 1 1 0 0 拓扑排序算法演示1 0 v20 v5v6 v1 v3 v2 v4 v5拓扑排序序列：拓扑排

5、序序列：14增加一个存放各顶点入度的数组indegree；(1)扫描indegree,将入度为零的顶点入栈;(2)while(栈非空)弹出栈顶元素vi并输出;检查vi的出边表,将每条出边的终点vj的入度减1,若vj的入度减至0,则vj入栈;(3)若输出的顶点数小n,则“有回路”；否则正常结束。拓扑排序算法概要15void FindInDegree(ALGraph G,int indegree)int i;ArcNode*p;for(i=0;iadjvex+;p=p-next;求各顶点入度的算法详解16Status TopologicalSort(ALGraph G)SqStack S;int

6、count,k,i;ArcNode*p;int indegreeMAX_VERTEX_NUM;FindInDegree(G,indegree);/对各顶点求入度InitStack(S);for(i=0;inextarc)k=p-adjvex;if(!(-indegreek)Push(S,k);if(count G.Vexnum)return ERROR;else return OK;/TopologicalSort接上页 拓扑排序算法详解18 拓扑算法分析设AOV网有n个顶点，e条边。初始建立入度为0 的顶点栈，要检查所有顶点一次，执行时间为O(n)；排序中，若AOV网无回路，则每个顶点入、出

7、栈各一次，每个边表结点被检查一次，执行时间为O(n+e)；拓扑排序算法的时间复杂度为O(n+e)。10.6.1 拓扑排序 10.6.2 关键路径10.6 有向无环图的应用20AOE网(Activity On Edge Network)：带权的有向图，顶点表示事件,边表示活动，权表示活动持续的时间。AOV网(Activity On Vertex Network)：带权的有向图，顶点表示活动，边表示活动之间的关系的网称为顶点活动网。21AOE网的特点(1)表示实际工程计划的AOE网应该是无回路的;(2)只有一个入度为零的顶点(称作源点),表示整个活动开始（工程开始点）;(3)只有一个出度为零的顶点

8、(称作汇点)表示整个活动结束（工程完成点）。22AOE网图示讨论：(1)整个工程至少需要多少时间？(2)哪些活动是影响工程进度的关键？v1v2V3v8v9v6201210151012v4v520v722212源点汇点23AOE网图示答案：最短时间（完成工程至少需要的时间）是从源点到汇点的最长路径长度（所经过的边上权值之和）。最长路径上的活动是影响工程进度的关键，称为关键活动（加快关键活动可以缩短工期）。v1v2V3v8v9v6201210151012v4v520v722212源点汇点24在AOE网中，有些活动可以同时进行，由关键活动构成的从开始到完成的路径；也是路径长度最长的路径。长度最长的路

9、径（路径中边的权值之和最大）称为关键路径。关键路径延迟就会影响整个工期的活动，关键路径上的活动都是关键活动。关键活动25讨论：关键活动延长是否必然影响工期？关键活动缩短是否必然缩短工期？结论：关键活动延长必然影响工期；关键活动缩短不一定能缩短工期。v1v2V3v8v9v6201210151012v4v520v722212261.事件Vk的最早发生时间是从源点V1到Vk的最长路径长度，记作ve(k)。这个长度决定了所有从顶点Vk发出的活动能够开工的最早时间。事件的最早发生时间与最迟发生时间2.事件Vk的最迟发生时间是指在不推迟整个工期的前提下,事件Vk允许的最晚发生时间。等于:Vn的最早发生时间

10、ve(n)减去vk到vn的最长路径长度，记作 vl(k)。271.若活动ai是由弧表示，则活动ai的最早开始时间应等于事件vk的最早发生时间，ei=vek。活动的最早开始时间与最晚开始时间2.活动ai的最晚开始时间是指，在不推迟整个工期的前提下，ai必须开始的最晚时间。若ai由弧表示，则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。因此，等于vj的最迟发生时间减去的持续时间，li=vlj-dut。28活动活动ai的松弛时间的松弛时间（时间余量时间余量）：ai的最晚开始时间与ai的最早开始时间之差：l(i)-e(i)。显然，松弛时间（时间余量）为松弛时间（时间余量）为0的活动为关键的活动

11、为关键活动。活动。29 关键活动 活动的最早开始时间与最晚开始时间的性质最早开始时间与最晚开始时间相等的活动，即e(i)=l(i)，为关键活动。目的就是要找出关键活动，为缩短工期提供帮助。v1v2V3v8v9v6201210151012v4v520v722212301.求出每个事件i的最早发生时间ve(i)和最晚发生时间vl(i)；2.设活动ai所对应的边为,dut()表示其持续时间,用如下公式计算活动ai的最早开始时间e(i)和最晚开始时间l(i)：e(i)=vej;l(i)=vlk-dut()求关键活动的算法要点3.比较e(i)和l(i)，两者相等的活动即为关键路径上的关键活动。311.公

12、式公式：设活动：设活动ai=弧弧的权定义为活动的持续的权定义为活动的持续时间时间dut()，则有下式成立：，则有下式成立：e(i)=ve(j)，l(i)=vl(k)-dut()。若若e(i)=l(i)，则活动，则活动ai就是关键路就是关键路径上的关键活动。径上的关键活动。2.求求ve(i):用拓扑排序求各事件的最早发生时间，有：用拓扑排序求各事件的最早发生时间，有：ve(j)=Maxve(i)+dut(),T，2jn，T为所有以为所有以j为头的弧的集合，初始条件为头的弧的集合，初始条件ve(1)=0。i3.求求vl(i):用逆拓扑排序求各事件的最晚发生时间，有：用逆拓扑排序求各事件的最晚发生时

13、间，有：vl(i)=Minvl(j)-dut()，S，1in-1，S为所有以为所有以i为尾的弧的集合，初始条件为尾的弧的集合，初始条件vl(n)=ve(n)。j 求关键活动的算法要点32V1V2 V3V4V5 V6V7V8 V9V10(a1a2a3)(a4)(a5a6)(a7)(a8)(a9a10)(a11a13)(a12)(a14)ve：04327813101521e：(0 0 0)(4)(3 3)(2)(7)(8 8)(13 13)(10)(15)vl：04347813111621关键活动：关键活动：a1、a2、a4、a6、a8、a9、a13；关键路径：关键路径：V1V2V5V7V10和和

14、 V1V3V6V7V10。21V1V2V3V6V4V5V7V8V9V10a1=4a2=3a3=2a4=3a5=3a6=5a9=5a12=5a7=4a8=6a10=2a11=1a13=8a14=5l：(0 0 2)(4)(4 3)(4)(7)(8 9)(15 13)(11)(16)21例：关键路径33例：关键路径34例：关键路径35求关键路径的基本步骤如下：(1)对图中顶点进行拓扑排序，求出每个事件的最早发生时间ve(i)；(2)按逆拓扑序列求每个事件的最晚发生时间vl(i)；(3)求出每个活动ai的最早开始时间e(i)和最晚发生时间l(i)；(4)找出e(i)=l(i)的活动ai，即为关键活动

15、。可通过修改拓扑排序算法，求出每个事件的最早发生时间ve(i)：36 关键路径算法所用数据结构float ven,vln;/记录事件的最早发生时间和最迟发生时间邻接表的存储表示#define MAX_VERTEX_NUM 20(1)边表：typedef struct ArcNode int adjVEx;/该弧所指向的顶点的位置struct ArcNode *nextarc;/指向下一条弧的指针InfoType info;/存权值 ArcNode;37(2)顶点表：typedef struct VNode VErtexType data;/顶点信息ArcNode *firstarc;/指向第一

16、条依附该顶点的弧 VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList VErtices;int VExnum,arcnum;int kind;/图的种类标志 ALGraph;ALGraph G;38status TopologicalOrder(ALGraph G,Stack&T)/有向网G采用邻接表存储结构，/求各顶点事件的最早发生时间ve(全局变量)。/T为拓扑序列定点栈，S为零入度顶点栈。/若G无回路，则用栈T返回G的一个拓扑序列，/且函数值为OK，否则为ERROR。关键路径算法详解见下页39Stack S;int count=0,k;c

17、har indegree40;ArcNode*p;InitStack(S);FindInDegree(G,indegree);for(int j=0;jG.vexnum;+j)/建零入度顶点栈Sif(indegreej=0)Push(S,j);/入度为0者进栈InitStack(T);/建拓扑序列顶点栈Tcount=0;接上页见下页 关键路径算法详解40for(int i=0;inextarc)k=p-adjvex;/对j号顶点的每个邻接点的入度减1 关键路径算法详解接上页见下页41if(-indegreek=0)Push(S,k);/若入度减为0，则入栈if(vej+p-info vek)v

18、ek=vej+p-info;if(countG.vexnum)return ERROR;else return OK;/TopologicalOrder 关键路径算法详解接上页见下页4243Status CriticalPath(ALGraph G)/G为有向网，输出G的各项关键活动。Stack T;int a,j,k,el,ee,dut;char tag;ArcNode*p;if(!TopologicalOrder(G,T)return ERROR;for(a=0;anextarc)k=p-adjvex;dut=p-info;/dutif(vlk-dut vlj)vlj=vlk-dut;关键

19、路径算法详解45for(j=0;jnextarc)k=p-adjvex;dut=p-info;ee=vej;el=vlk-dut;tag=(ee=el)?*:;printf(j,k,dut,ee,el,tag);/输出关键活动return OK;/CriticalPath 关键路径算法详解4647 算法分析在拓扑排序求Vei和逆拓扑有序求Vli时,所需时间为O(n+e)；求各个活动的ek和lk时所需时间为O(e)；总共花费时间仍然是O(n+e)。关键路径算法分析在拓扑排序求Vei和逆拓扑有序求Vli时,所需时间为O(n+e)；求各个活动的ek和lk时所需时间为O(e)；总共花费时间仍然是O(n

20、+e)。49例：对上图所示的AOE-网计算关键路径的过程如下(1)计算各事件的最早开始时间：ve(0)=0 ve(1)=maxve(0)+dut()=6 120367458a1=6a2=4a3=5a6=2a5=1a8=7a9=4a4=1a7=9a10=2a11=4图7.2450120367458a1=6a2=4a3=5a6=2a5=1a8=7a9=4a4=1a7=9a10=2a11=4图7.24ve(2)=maxve(0)+dut()=4 ve(3)=maxve(0)+dut()=5 ve(4)=maxve(1)+dut(),ve(2)+dut()=7 ve(5)=maxve(3)+dut()

21、=7ve(6)=maxve(4)=dut()=16 ve(7)=maxve(4)+dut()=14 ve(8)=maxve(6)+dut(),ve(7)+dut()=18 51(2)计算各事件的最迟开始时间：vl(8)=ve(8)=18 vl(7)=minvl(8)-dut()=14vl(6)=minvl(8)-dut()=16 vl(5)=minvl(7)-dut()=10 vl(4)=minvl(6)-dut(),vl(7)-dut()=7 120367458a1=6a2=4a3=5a6=2a5=1a8=7a9=4a4=1a7=9a10=2a11=4图7.24vl(3)=minvl(5)-

22、dut()=8 vl(2)=minvl(4)-dut()=6 vl(1)=minvl(4)-dut()=6 vl(0)=minvl(1)-dut(),vl(2)-dut(),vl(3)-dut()=0120367458a1=6a2=4a3=5a6=2a5=1a8=7a9=4a4=1a7=9a10=2a11=4图7.2453120367458a1=6a2=4a3=5a6=2a5=1a8=7a9=4a4=1a7=9a10=2a11=4图7.24(3)计算各活动的最早开始时间：e(a1)=ve(0)=0 e(a2)=ve(0)=0 e(a3)=ve(0)=0 e(a4)=ve(1)=6 e(a5)=

23、ve(2)=4 e(a6)=ve(3)=5 e(a7)=ve(4)=7 e(a8)=ve(4)=7 e(a9)=ve(5)=7 e(a10)=ve(6)=16 e(a11)=ve(7)=14 54(4)计算各活动的最迟开始时间：l(a11)=vl(8)-dut()=14l(a10)=vl(8)-dut()=16 l(a9)=vl(7)-dut()=10l(a8)=vl(7)-dut()=7 l(a7)=vl(6)-dut()=7 l(a6)=vl(5)-dut()=8 120367458a1=6a2=4a3=5a6=2a5=1a8=7a9=4a4=1a7=9a10=2a11=4图7.2455l

24、(a5)=vl(4)-dut()=6 l(a4)=vl(4)-dut()=6 l(a3)=vl(3)-dut()=3 l(a2)=vl(2)-dut()=2 l(a1)=vl(1)-dut()=0 120367458a1=6a2=4a3=5a6=2a5=1a8=7a9=4a4=1a7=9a10=2a11=4图7.245657106748a1a4a7a8a11a10图7.25可以看出，该图中有两条关键路径：一条是由a1,a4,a7,a10组成的关键路径一条是由a1,a4,a8,a11组成的关键路径例子：以下图AOE网为例，求关键活动和关键路径。58 a a1 1 =6 6 a a2 2=2 2

25、a a3 3=4 4 a a4 4=3 3 a a5 5=5 5 a a6 6=8 8 a a7 7=7 7 a a8 8=2 2 a a9 9=6 6 a a1 10 0=4 4 a a1 11 1=5 5 a a1 12 2=7 7 V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 例子（续）：首先，求各事件和活动的最早、最迟发生时间：59（a）顶点发生时间）顶点发生时间 顶点顶点 vei vli v1 0 0 v2 6 6 v3 2 4 v4 4 4 v5 9 9 v6 12 12 v7 16 16 v8 18 18 v9 20 20 v10 25 25 （b）活动发生时间）

26、活动发生时间 活动活动 ei li li-ei a1 0 0 0 a2 0 2 2 a3 0 0 0 a4 6 6 0 a5 2 4 2 a6 4 4 0 a7 9 9 0 a8 9 16 7 a9 12 12 0 a10 16 16 0 a11 20 20 0 a12 18 18 0 例子（续）：然后，根据活动的最早、最迟发生时间确定关键活动：60（b）活动发生时间）活动发生时间 活动活动 ei li li-ei a1 0 0 0 a2 0 2 2 a3 0 0 0 a4 6 6 0 a5 2 4 2 a6 4 4 0 a7 9 9 0 a8 9 16 7 a9 12 12 0 a10 16

27、 16 0 a11 20 20 0 a12 18 18 0 由由右右表表可知可知，a1，a3，a4，a6，a7，a9，a10，a11，a12为关键活动为关键活动。例子（续）：最后，根据关键活动得到关键路径：61a1，a3，a4，a6，a7，a9，a10，a11，a12为关键活动为关键活动。a a1 1 =6 6 a a3 3=4 4 a a4 4=3 3 a a6 6=8 8 a a7 7=7 7 a a9 9=6 6 a a1 10 0=4 4 a a1 11 1=5 5 V1 V2 V4 V5 V6 V7 V8 V9 V10 a a12 12=7 7 62本章小结本章基本内容本章基本内容 图的存储图的存储 深度优先深度优先 图的遍历图的遍历 广度优先广度优先 图的应用图的应用 图与树图与树 邻接矩阵邻接矩阵 邻接表邻接表 生成树生成树 最短路径最短路径 最小生成树最小生成树 Prime 算法算法 Kruscal 算算拓扑排序拓扑排序 关键路径算法关键路径算法 相关相关概念概念 基于邻接表实现算法基于邻接表实现算法 图图 63The end