数据结构课件：13 第五章 图2

1、 第五章 图5.1 基本概念5.2 图的存储结构5.3 图的遍历5.4 拓扑排序5.5 关键路径 5.6 最短路径5.7 最小支撑树5.8 图的应用5.5.1 基本概念 边表示活动(Activity) 边的权值表示活动的持续时间(Duration) 顶点表示入边的活动已完成，出边的活动可以开始的状态，也称为事件(Event) 这样的有向无环的带权图叫做AOE (Activity On Edges)网。例 某工程源点：表示整个工程的开始（入度为零）。汇点：表示整个工程的结束（出度为零）。完成整个工程至少需要多少时间？为缩短工程的时间，应当加快哪些活动？325140867a1=6a8=7a7=9a

2、6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2汇点源点从源点到各顶点的路径可能不止一条，路径长度也可能不同。只有各条路径上所有活动都完成了，整个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径。路径长度：指路径上的各边权值之和。关键活动：关键路径上的活动。325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2汇点源点 关键活动有关的量： 事件vj的最早发生时间ve(j): 从源点v0到vj的最长路径长度。 事件vj的最

3、迟发生时间vl(j):保证汇点的最早发生时间不推迟的前提下，事件vj允许的最迟开始时间，等于ve(n-1)减去从vj到vn-1最长路径长度。325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2汇点源点 ve(0)=0ve(1)= 6ve(2)= 4ve(3)= 5ve(4)= 7ve(5)= 7ve(6)= 16ve(7)= 14ve(8)= 18vl(8)= 18vl(7)= 14vl(6)= 16vl(5)= 10vl(4)= 7vl(3)= 8vl(2)= 6vl(1)= 6vl(0)= 0 关键活动有关的量： 活动ai的最早开始

4、时间e(i): 设活动ai在有向边上, e(i)是从源 点v0到vj的最长路径长度。因此e(i)=ve(j)。325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2汇点源点 关键活动有关的量： 活动ai的最迟开始时间l(i): l(i) 是在不会引起时间延误的前提下，该活动允许的最迟开始时间。设活动ai在有向边上, 则 l(i)= vl(k)-weight()325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2汇点源点 aie(i)l(i) 0 0 0 6 4 5 7 7 7 16

5、 14 0 2 3 6 6 8 7 7 10 16 14 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 关键活动： l(i) e(i) 表示活动ak 是没有时间余量的关键活动。325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2汇点源点为找出关键活动, 需要求各个活动的 e(i) 与 l(i)，以判别是否 l(i) e(i) 为求得e(i) 与 l(i)，需要先求得从源点V0到各个顶点Vj 的 ve(j) 和 vl(j)。求关键活动算法求关键活动的基本步骤：对AOE网进行拓扑排序，按拓扑次序求出各顶点事件的最早发

6、生时间ve，若网中有回路，则终止算法； 按拓扑序列的逆序求各顶点事件的最迟发生时间vl;根据ve和vl的值，求各活动的最早开始时间e(i)与最迟开始时间l(i)，若e(i)=l(i)，则i是关键活动。 例 求关键活动 第1步ve(k)ve(0)0 k=0maxve(j)+ weight() E(G), k=1, 2, , n-1325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2汇点源点按拓扑正序递推: ve(0)=0ve(1)= ve(0)+weight()=0+6=6ve(2)= ve(0)+weight()=0+4=4ve(3)=

7、 ve(0)+weight()=0+5=5ve(4)= maxve(1)+ weight()， ve(2)+ weight()=max6+1,4+1=7ve(5)= ve(3)+weight()=5+2=7ve(6)= ve(4)+weight()=7+9=16ve(7)= maxve(4)+ weight()， ve(5)+ weight()=max7+7,7+4=14ve(8)= maxve(6)+ weight()， ve(7)+ weight()=max16+2,14+4=18 例 求关键活动 第2步vl(j)ve(n-1) j=n-1minvl(k)- weight() E(G),

8、j= n-2, n-3,0325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2汇点源点按拓扑逆序递推: vl(8)= ve(8)=18vl(7)= vl(8)-weight()=18-4=14vl(6)= vl(8)-weight()=18-2=16vl(5)= vl(7)-weight()=14-4=10vl(4)= minvl(7)- weight()， vl(6)- weight() =min14-7,16-9=7vl(3)= vl(5)-weight()=10-2=8vl(2)= vl(4)-weight()=7-1=6vl(1

9、)= vl(4)-weight()=7-1=6vl(0)= minvl(1)- weight()， vl(2)- weight(), vl(3)- weight() = min6-6,6-4,8-5=0 aie(i)l(i)li-ei 0 0 0 6 4 5 7 7 7 16 14 0 2 3 6 6 8 7 7 10 16 14 0 2 3 0 2 3 0 0 3 0 0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 例 求关键活动 第3步： e(i)=ve(j), l(i)=vl(k)-weight()325140867a1=6a8=7a7=9a6=2a4=1a5=

10、1a3=5a2=4a9=4a11=4a10=2汇点源点算法CriticalPath ()/* 图的关键路径算法 */CPath1计算事件的最早发生时间 FOR i = 1 TO n DO ve i 0. FOR i = 1 TO n1 DO/*（1）按顶点的拓扑序列计算各事件的最早发生时间*/ (padjacent(Head i) . WHILE p DO(k VerAdj (p) .IF (vei + cost (p) vek ) THENvek vei + cost (p) .plink(p)CPath2计算事件的最迟发生时间 FOR i = 1 TO n DO vli ven . FOR

11、 i = n1 TO 1 STEP 1 DO /*（2）按拓扑逆序计算事件的最迟发生时间*/ (padjacent (Headi) .WHILE p DO(kVerAdj(p) .IF (vlk cost (p) vli ) THENvli vlk cost(p) .plink(p)CPath3求诸活动的最早开始时间和最迟开始时间 FOR i = 1 TO n DO (padjacent (Head i) .WHILE p DO(kVerAdj (p) .evei .lvlk cost(p) .IF l = e THEN PRINT is Critical Activity! plink(p)

12、 时间复杂性： 对定点进行拓扑排序的时间复杂性为O(n+e), 以拓扑排序求vei和以拓扑逆序求vli时, 所需时间为均为O(e), 求各个活动的ek和lk的时间复杂度为O(e), 整个算法的时间复杂性是O(n+e)。定理 5.3 任意的非空AOE网至少存在一条关键路径。 推论 5.1 假设边属于AOE网，则有且如果属于某一条关键路径，则有 第五章 图5.1 基本概念5.2 图的存储结构5.3 图的遍历5.4 拓扑排序5.5 关键路径 5.6 最短路径5.7 最小支撑树5.8 图的应用5.6 最短路径问题 两顶点间可能存在多条路径，每条路径经过的边数不同，每条路径的各边权值之和也不同。 从一个

13、指定的顶点到达另一指定顶点的路径上各边权值之和最小的路径被称为最短路径，这类问题亦称为最短路径问题。 单源(由一个指定顶点到其他顶点)最短路径 无权最短路径 正权最短路径 负权最短路径每对顶点之间的最短路径问题5.6.1 无权最短路径问题无权所有边的权值都为1源点到各顶点的路径所经历的边的数目就是路径的长度相对于源点由近及远依次求各顶点的最短路径算法思想：设Di为源点S到顶点 i 的最短路径长度访问初始顶点S，即令DS=0。从S出发，找最短路径为1的顶点，即S的所有邻接顶点w，令Dw=DS+1从上步访问的顶点w出发，找最短路径为2的顶点，即w未被访问的邻接顶点v，令Dv=Dw+1继续上述过程，

14、直至处理完所有顶点。1V12V63V51V32V43V20SV0 例V1V6V5V3V4V21122330SV0上述过程中，访问顶点的次序与对图进行广度优先遍历的次序是一致的;初始时，令Dw=-1，当Dw由-1变成一个正整数时，表示从源点到w的最短路径已求完，Dw值就是最短路径长度,实现时使用数组dist 存储;为了找到最短路径，使用path 存储从源点到顶点 i 的最短路径上最后一个经历的顶点。宽度优先遍历 将所有顶点的visited值置为0, 访问初始顶点v0 ，置visitedv0=1，v0入队； 检测队列是否为空，若队列为空，则迭代结束； 从队头取出一个顶点v，检测其每个邻接节点w：

15、如果w未被访问过，则 访问w； 将visitedw值更新为1； 将w入队； 执行步骤 。算法ShortestPath(v, n)/* 计算从顶点v到其他各顶点的最短路径*/SPath1初始化 CREATQ(Q) . /* 创建一个队列 */ FOR i = 1 TO n DO (pathi -1. disti -1.) distv 0 . Qv.SPath2求从顶点v到其他各顶点的最短路径 WHILE NOT(ISEMTQ(Q) DO ( u Q . /* 队头顶点u出队 */ p adjacent (Headu) . /* p为u的边链表的头指针 */ WHILE p DO ( k VerA

16、dj (p) . IF (distk = -1) THEN ( Q k. / 将u的未访问的邻接顶点入队 distk distu + 1. /修改其path值和dist值 pathk u)p link(p) . ) ) 1V12V63V51V32V43V20SV0 在最短路径的计算中，一个顶点入队出队各一次，时间复杂性为O(n)，而对每个顶点，都要对它的边链表进行遍历，其遍历邻接表的开销为O(e)，于是整个算法的时间复杂性为O(n+e)。 5.6.2 正权最短路径问题问题： 给定一个带权有向图D（限定各边上的权值大于或等于0）与源点v，求从v到D中其它顶点的最短路径。宽度优先策略还可行吗？最短

17、路径不一定恰好就是连接这两个顶点的边(若此边存在)，而可能是一条包括一个或多个中间顶点的路径。v0v1v2283 Dijkstra算法基本思想：将图中所有顶点分成两个集合，第一个集合S包括已确定最短路径的顶点，第二个集合T包括尚未确定最短路径的顶点。按照最短路径长度递增的顺序逐个把第二组的顶点加到第一组中去，直至从源点出发可以到达的所有顶点都包括到第一组中。 Dijkstra算法描述初始时（S为初始顶点）, Ds=0且 i S，有Di =。在未访问顶点中选择Dv最小的顶点v，访问v，令 Sv=1。依次考察v的邻接顶点w，若 Dv+weight() Dw ， 则改变Dw的值，使Dw = Dv +

18、 weight() 。重复 ，直至所有顶点被访问。为了找到最短路径，使用path 存储从S到 i 的最短路径上最后一个经历的顶点。定理7.1 Dijkstra算法可以按照非递减次序依次得到各顶点的最小路径长度。 当前正在访问的节点v， Dv为源点到v的最短距离，对应的最短路径是由已访问节点组成；按照访问的次序，该算法将生成一个节点序列，排在前面的节点距源点的距离小于等于排在后面节点距源点的距离。引入一个辅助数组dist。它的每一个分量disti表示当前找到的从源点s到顶点i 的最短路径的长度。初始状态： dists=0, 对其它节点i有disti=+ 。 pathi记录s到i最短路径中i的前驱

19、节点编号 例 1325810204530120234012340243105134303822541002024412 spathdist0000003421 01325810204530120234在未访问顶点中选择Dv最小的顶点v，访问v，令 Sv=1。依次考察v的邻接顶点w，若 Dv+weight() Dw ，则改变Dw的值，使Dw = Dv + weight() 。重复 ，直至所有顶点被访问。0133023431325810204530120234spathdist10000034210303v0v0spathdist100010342103028311v0v0v1v132581330

20、02343028111325810204530120234 03421spathdist1100103028311v0 v1v1 v013258102045301202343120415813234231103421spathdist1100102315311v0v3v1v3132581020453012023431204158132342311120415813234231131325810204530120234spathdist1100102315311v0v3v1v3spathdist111110342102315311v0v3v1v3Dijkstra算法: 按照非递减顺序依次得到各顶

21、点的最小路径长度。120415813234231131325810204530120234定理5.4 Dijkstra算法可以按照非递减次序依次得到各顶点的最小路径长度。 证明：归纳法算法得到的路径值是各顶点的最小路径长度。算法得到的路径值是按非递减次序得到的。算法DShortestPath(n, v)/* 计算v到其他各顶点的最短路径 */DSPath1初始化 FOR i = 1 TO n DO ( pathi-1. disti max. si 0. )/ 数组si记录i是否被访问过 distv 0. sv 1. p adjacent (Headv) . u v. / u为即将访问的顶点DS

22、Path2求从初始顶点v到其他各顶点的最短路径 FOR j = 1 TO n-1 DO / 求从v到其他各顶点的最短路径 (WHILE p DO /修改u邻接顶点的path值和dist值 ( kVerAdj (p) . IF ( sk 1 AND distu + cost(p) 0 AND disti ldist AND si = 0 ) THEN( ldist disti . u i. ) su 1./ 访问u p adjacent (Headu) ) / p为u的边链表的头指针该算法的时间复杂性为O(n2+e)，也可认为是O(n2)时间复杂性分析5.6.3 每对顶点间的最短路径问题：已知一

23、个各边权值均大于0的带权有向图，对每一对顶点 vi vj，求vi 与vj间的最短路径和最短路径长度。可依次把每个顶点作为源点，执行n次Dijkstra算法。Floyd算法：定义一个n阶方阵序列： A(-1), A(0), , A(n-1).Floyd算法的基本思想：设邻接矩阵存储图，定义初始矩阵A(-1) ij = Edgeij；1、求A(0),即从vi到vj 经由顶点可以是v0的最短路径长度；2、求A(1),即从vi 到vj 经由顶点可以是v0, v1的最短路径长度； n、求A(n-1),即从vi 到vj 经由顶点可以是v0, v1,vn-1的最短路径长度； 其中 A(k) ij = min

24、 A(k-1)ij， A(k-1)ik + A(k-1)kj , k = 0,1, n-1 Floyd算法的基本思想： 定义一个n阶方阵序列： A(-1), A(0), , A(n-1). 其中 A(-1) ij = Edgeij； A(k) ij = min A(k-1)ij， A(k-1)ik + A(k-1)kj , k = 1, n A(-1) ij是从顶点vi 到vj , 中间顶点是v0的最短路径的长度, A(k) ij是从顶点vi 到vj , 中间顶点的序号不大于k的最短路径的长度, A(n-1)ij是从顶点vi 到vj 的最短路径长度。上式每迭代一次，在从顶点i到顶点j之间的最短

25、路径就多考虑一个顶点。经过n次迭代后， A(k) i, j的值就是从顶点i到顶点j之间的最短路径。 从A(3)知，顶点1到0的最短路径长度为a10 = 11,其最短路径看 path10 = 2，path12 = 3，path 13 = 1, 表示顶点0 顶点2 顶点3 顶点1; 从顶点1到顶点0最短路径为,。 Floyd算法允许图中有带负权值的边，但不许有包含带负权值的边组成的回路。 从A(3)知，顶点1到0的最短路径长度为a10=11,其最短路径 path10=2，path12=3，path 13=1, 表示顶点0顶点2 顶点3 顶点1;从顶点1到顶点0最短路径为,。 算法 AllLengt

26、h ( n )/* 求每对顶点间的最短路径 */ALength1初始化 FOR i=0 TO n-1 DO / 矩阵A和path初始化FOR j=0 TO n-1 DO( Aij edgeij ./ 初始化的A即A(-1) IF ( ij AND Aij max ) THENpathiji . ELSEpathij -1.)ALength2求图中任意两顶点的最短路径 FOR k=0 TO n-1 DO /从A(-1)开始针对每个k逐步构造A(n-1) FOR i=0 TO n-1 DOIF (ik) THEN FOR j=0 TO n-1 DO IF(j k AND j i AND Aikma

27、x AND Akjmax AND Aik+AkjAij) THEN ( Aij Aik + Akj . pathijpathkj .) Floyd算法的时间复杂度为O(n3)，与调用n次Dijkstra算法求每对顶点的最短路径的时间复杂度相同。 但Dijkstra算法仅针对正权图，而Floyd算法允许图中有带负权值的边，但不许有包含带负权值的边组成的回路；且Floyd算法更简单易于理解。 本章给出的求解最短路径的算法，不仅适用于带权有向图，对带权无向图也可以适用。因为带权无向图可以看作是有往返二重边的有向图。 第五章 图5.1 基本概念5.2 图的存储结构5.3 图的遍历5.4 拓扑排序5.5

28、 关键路径 5.6 最短路径5.7 最小支撑树5.8 图的应用 5.7 最小支撑树1、基本概念2、生成最小支撑树算法 Prim算法 Kruskar算法最小支撑树基本概念 对于一个无向网络无向加权连通图N=(V,E,C)(C表示该图为权图)，其顶点个数为|V|=n，图中边的个数为|E| ，我们可以从它的|E|条边中选出n-1条边，使之满足 （1）这n-1条边和图的n个顶点构成一个连通图。 （2）该连通图的代价是所有满足条件(1)的连通图的代价的最小值。 这样的连通图被称为网络的最小支撑树( Minimum-cost Spanning Tree )。 最小支撑树的性质最小支撑树中没有回路 若MST

29、 的边集中有回路，显然可通过去掉回路中某条边而得到花销更小的MST最小支撑树是一棵有|V| - 1条边的树最小支撑树的边集支撑起了图中所有顶点，且边集的代价最小最小支撑树的应用使连接电路板上一系列接头所需焊接的线路最短在n个城市间建立造价最低的通讯网络 5.7 最小支撑树1、基本概念2、生成最小支撑树算法 Prim算法 Kruskar算法MST性质：N=(V, E, C)是一个连通网，U是V的一个非空子集，若u, v满足weight(u, v)=min weight(u0, v0) | u0U, v0V-U则必存在N的一棵最小支撑树，该支撑树中包括边(u, v)。 U V-U uv1、普里姆(

30、Prim)算法(逐点加入) 设N=(V,E,C)为连通网，TE是N的最小支撑树MST的边的集合，U为MST顶点集。 U=uo(uoV), TE= ； 找到满足weight(u,v)minweight(u1,v1)|u1U, v1V-U, 的边，把它并入TE，同时v并入U； 反复执行 ,直至 V=U , 算法结束。 4316504535562217 U V-U例431650453556221702143165045355622174316504535562217 U V-U402150214053221402154316504535562217 U V-U41053522143165045355

31、62217 U V-U4053221410535221 U V-U431650453556221743104535221假设用邻接矩阵存储图。普里姆算法的实现需要增设两个辅助数组closedgen和TEn-1 .closedgen的每个数组元素由两个域构成：Lowcost和Vex，其定义如下：如果 ，则 = 而closedgev.Vex存储的是该边依附在U 中的顶点u.如果 ，则 数组TEn-1是最小支撑树的边集合，每个数组元素TEi表示一条边，TEi由三个域head、tail和cost构成，它们分别存放边的始点、终点和权值。 432156452314326515645562317131413

32、1641642314216452314326515645562317 Vclosedge123456UV-UVexLowcost-101611151max1max12 ,3 ,4 ,5,64326515645562317 U V-UPrim: FOR i = 1 TO n DO ( Lowcost (closedgei)edge1i . Vex (closedgei) 1) Vex (closedge1) -1. count 1. Vclosedge123456UV-UVexLowcost-101611151max1max12 ,3 ,4 ,5 ,6v 0. / 求当前权值最小的边和该边的终点

33、vminmax. FOR j = 1 TO n DO IF (vex (closedgej) -1 AND Lowcost(closedgej) min ) ( v j. min Lowcost (closedgej) ) Vclosedge123456UV-UVexLowcost-1016-10151max1max1,32, 4 ,5 ,6If v0 THEN / v加入U中 ( head(TEcount) Vex (closedgev) . tail (TEcount) v. cost (TEcount) Lowcost(closedgev) . count count +1./ 计数器加

34、1 Lowcost (closedgev) 0. / 修改域值 Vex(closedgev) -1./ 顶点v进入集合U Vclosedge123456UV-UVexLowcost-1035-101535341,32,4 ,5,6 4326515645562317 U V-U FOR j = 1 TO n DO /修改某些顶点的值 IF(Vex(closedgej) -1 AND edgevj Lowcost(closedgej) THEN ( Lowcost(closedgej) edgevj . Vex(closedgej) v. ) )算法Prim( )/* 构造最小支撑树的Prim算法

35、 */Prim1初始化邻接矩阵 FOR i = 1 TO n DO FOR j = 1 TO n DO IF (edgeij = 0) edgeij = max; / max是预定义常数Prim2以顶点1为初始顶点，初始化数组closedge FOR i = 1 TO n DO ( Lowcost (closedgei)edge1i . Vex (closedgei) 1) Vex (closedge1) -1./ 顶点1进入集合U count 1. / 支撑树的边记数器countPrim3构造图的最小支撑树 FOR i =2 TO n DO / 循环n-1次 ( v 0. minmax. / 求当前权值最小的边和该边的终点v FOR j = 1 TO n DO IF (vex (closedgej) -1 AND Lowcost(closedgej) min ) THEN ( v j. min Lowcost (closedgej) . ) IF v0 THEN /将该边加入TE中，点v加入集合U中 ( head(TEcount) Vex (closedgev) . tail (TEcount) v. cost (TEcount) Lowcost(closedgev) . count count +1./ 计数器加1 Lowcost (clos