数据结构课件：第5章 图2

1、第五章 图 5.1 基本概念 5.2 图的存储结构 5.3 图的遍历 5.4 拓扑排序 5.5 关键路径 5.6 最短路径 5.7 最小支撑树,5.6 最短路径问题 两顶点间可能存在多条路径，每条路径经过的边数不同，每条路径的各边权值之和也不同。 从一个指定的顶点到达另一指定顶点的路径上各边权值之和最小的路径被称为最短路径，这类问题亦称为最短路径问题。,单源(由一个指定顶点到其他顶点)最短路径 无权最短路径 正权最短路径 每对顶点之间的最短路径问题,5.6.2 正权最短路径问题 给定一个带权图D与源点v，求从v到D中其它顶点的最短路径, 限定各边的权值为正实数。,Dijkstra算法思想 按路

2、径长度非递减的次序，逐步产生最短路径的算法，解决正权单源最短路径问题。 首先求出从源点v出发，长度最短的一条最短路径；再参照它求出长度次短的一条最短路径；依此类推，直到求出从顶点v到其它各顶点的最短路径为止。,Dijkstra算法描述 初始时（S为初始顶点）, Ds=0且 i S，有Di =。 在未访问顶点中选择Dv最小的顶点v，访问v，令 Sv=1。 依次考察v的邻接顶点w，若 Dv+weight() 。 重复 ，直至所有顶点被访问。 为了找到最短路径，使用path 存储从S到 i 的最短路径上最后一个经历的顶点。,例,在未访问顶点中选择Dv最小的顶点v，访问v，令 Sv=1。 依次考察v的

3、邻接顶点w，若 Dv+weight() 。 重复 ，直至所有顶点被访问。,Dijkstra算法: 按照非递减顺序依次得到各顶点的最小路径长度。,正权单源最短路径问题的 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为即将访问的顶点,DSPath1初始化 FOR i = 1 TO n DO ( pa

4、thi-1. disti max. si 0. ) distv 0. sv 1. p adjacent (Headv) . u v. / u为即将访问的顶点,DSPath2求从初始顶点v到其他各顶点的最短路径 算法DSPath2第1部分 FOR j = 1 TO n-1 DO / 求从v到其他各顶点的最短路径 (WHILE p DO /修改u邻接顶点的path值和dist值 ( kVerAdj (p) . IF ( sk 1 AND distu + cost(p) distk ) THEN ( distk distu + cost(p) . pathk u. ) p link(p) ) /确定

5、即将被访问的顶点u,算法DSPath2第2部分 ldist max. FOR i = 0 TO n-1 DO IF ( disti 0 AND disti ldist AND si = 0 ) THEN (ldist disti . u i. ) su 1./ 访问u p adjacent (Headu) ) ,算法DSPath2第1部分 FOR j = 1 TO n-1 DO / 求从v到其他各顶点的最短路径 (WHILE p DO ( kVerAdj (p) . IF ( sk 1 AND distu + cost(p) distk ) THEN ( distk distu + cost(

6、p) . pathk u. ) p link(p) ),算法DSPath2第1部分 FOR j = 1 TO n-1 DO / 求从v到其他各顶点的最短路径 (WHILE p DO ( kVerAdj (p) . IF ( sk 1 AND distu + cost(p) distk ) THEN ( distk distu + cost(p) . pathk u. ) p link(p) ),算法DSPath2第2部分 ldist max. FOR i = 1 TO n DO IF ( disti 0 AND disti ldist AND si = 0 ) THEN (ldist dist

7、i . u i. ) su 1./ 访问u p adjacent (Headu) ) ,算法DSPath2第1部分 FOR j = 1 TO n-1 DO / 求从v到其他各顶点的最短路径 (WHILE p DO ( kVerAdj (p) . IF ( sk 1 AND distu + cost(p) distk ) THEN ( distk distu + cost(p) . pathk u. ) p link(p) ),算法DSPath2第2部分 ldist max. FOR i = 1 TO n DO IF ( disti 0 AND disti ldist AND si = 0 )

8、THEN (ldist disti . u i. ) su 1./ 访问u p adjacent (Headu) ) ,3,算法DSPath2第1部分 FOR j = 1 TO n-1 DO / 求从v到其他各顶点的最短路径 (WHILE p DO ( kVerAdj (p) . IF ( sk 1 AND distu + cost(p) distk ) THEN ( distk distu + cost(p) . pathk u. ) p link(p) ),算法DSPath2第2部分 ldist max. FOR i = 1 TO n DO IF ( disti 0 AND disti l

9、dist AND si = 0 ) THEN (ldist disti . u i. ) su 1./ 访问u p adjacent (Headu) ) ,该算法的时间复杂性为O(n2+e)，也可认为是O(n2),4,5.6.3 每对顶点间的最短路径 问题：已知一个各边权值均大于0的带权有向图，对每一对顶点 vi vj，求vi 与vj间的最短路径和最短路径长度。 可依次把每个顶点作为源点，执行n次Dijkstra算法。 Floyd算法： 定义一个n阶方阵序列： A(-1), A(0), , A(n-1).,Floyd算法的基本思想： 设邻接矩阵存储图，定义初始矩阵A(-1) ij = Edge

10、ij； 1、求A(0),即从vi到vj 经由顶点可以是v0的最短路径长度； 2、求A(1),即从vi 到vj 经由顶点可以是v0, v1的最短路径长度； n、求A(n-1),即从vi 到vj 经由顶点可以是v0, v1,vn-1的最短路径长度； 经过n次运算后，最后求得的就是从vi-vj的最短路径。 其中 A(k) ij = min A(k-1)ij， A(k-1)ik + A(k-1)kj , k = 0,1, n-1,例 求下图中每对顶点之间的最短路径。,A(k)ij = minA(k-1)ij, A(k-1)ik+ A(k-1)kj|0 k n-1,当i=j时，公式变为： A(k)ij

11、= minA(k-1)ii, A(k-1)ik+ A(k-1)ki|0 k n-1= 0,A(k)ij = minA(k-1)ij, A(k-1)ik+ A(k-1)kj|0 k n-1,当i=k或j=k时，公式变为： A(k)kj = minA(k-1)kj, A(k-1)kk+ A(k-1)kj | 0 k n-1 A(k)ik = minA(k-1)ik, A(k-1)ik+ A(k-1)kk | 0 k n-1,A(k)ij = minA(k-1)ij, A(k-1)ik+ A(k-1)kj|0 k n-1,A(k)ij = minA(k-1)ij, A(k-1)ik+ A(k-1)k

12、j|0 k n-1,0 1 2 3,0 1 10 3 0 9 2 3 4 0 6 6 0,0 1 2 3,A（1） ,A(k)ij = minA(k-1)ij, A(k-1)ik+ A(k-1)kj|0 k n-1,A(k)ij = minA(k-1)ij, A(k-1)ik+ A(k-1)kj|0 k n-1,求每对顶点之间的最短路径算法 template void Graph:allLength(const int n), for ( int i = 0; i j /缩短路径长度, 绕过 k 到 j,for ( int i = 0; i j / i 到 j 无路径 ,for ( int i

13、 = 0; i j / i 到 j 无路径 ,for ( int k = 0; k n; k+ ) for ( i = 0; i n; i+ ) for ( j = 0; j n; j+ ) if ( Aik + Akj Aij ) Aij = Aik + Akj; pathij = pathkj; ,for ( int k = 0; k n; k+ ) for ( i = 0; i n; i+ ) for ( j = 0; j n; j+ ) if ( Aik + Akj Aij ) Aij = Aik + Akj; pathij = pathkj; ,for ( int k = 0; k

14、n; k+ ) for ( i = 0; i n; i+ ) for ( j = 0; j n; j+ ) if ( Aik + Akj Aij ) Aij = Aik + Akj; pathij = pathkj; ,for ( int k = 0; k n; k+ ) for ( i = 0; i n; i+ ) for ( j = 0; j n; j+ ) if ( Aik + Akj Aij ) Aij = Aik + Akj; pathij = pathkj; ,从A(3)知，顶点1到0的最短路径长度为A10 = 11, 其最短路径看 path10 = 2，path12 = 3，pa

15、th 13 = 1, 表示顶点0 顶点2 顶点3 顶点1;从顶点1到顶点0最短路径为,。,0,Floyd算法的时间复杂度为O(n3)，与调用n次Dijkstra算法求每对顶点的最短路径的时间复杂度相同。 但Dijkstra算法仅针对正权图，而Floyd算法允许图中有带负权值的边，但不许有包含带负权值的边组成的回路；且Floyd算法更简单易于理解。,本章给出的求解最短路径的算法，不仅适用于带权有向图，对带权无向图也可以适用。因为带权无向图可以看作是有往返二重边的有向图。,第五章 图 5.1 基本概念 5.2 图的存储结构 5.3 图的遍历 5.4 拓扑排序 5.5 关键路径 5.6 最短路径 5

16、.7 最小支撑树,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 的边集中有回路，显然可通过去掉回路中

17、某条边而得到花销更小的MST 最小支撑树是一棵有|V| - 1条边的树 最小支撑树的边集支撑起了图中所有顶点，且边集的代价最小 最小支撑树的应用 使连接电路板上一系列接头所需焊接的线路最短 在n个城市间建立造价最低的通讯网络,5.7 最小支撑树 1、基本概念 2、生成最小支撑树算法 Prim算法 Kruskar算法,1 普里姆(Prim)算法（逐点加入） 设为N=(V,E,C)连通网，TE是N的最小支撑树的边的集合。 算法开始时，U= uo(uoV), TE= ； 找到满足 weight(u,v）minweight(u1,v1）| u1U, v1V-U, 的边，把它并入集合TE中，v同时并入U

18、。 反复执行 ,直至 V=U 时终止算法。,假设用邻接矩阵存储图。普里姆算法的实现需要增设两个辅助数组closedgen和TEn-1 . closedgen的每个数组元素由两个域构成：Lowcost和Vex，其定义如下： 如果 ，则 = 而closedgev.Vex存储的是该边依附在U 中的顶点u. 如果 ，则 数组TEn-1是最小支撑树的边集合，每个数组元素TEi表示一条边，TEi由三个域head、tail和cost构成，它们分别存放边的始点、终点和权值。,普里姆算法 /* 利用普里姆算法从顶点v1出发求出用邻接 矩阵Edge表示的图的最小支撑树，最小支撑树 的边集存于数组TE中*/,算法P

19、rim( ) /* 构造最小支撑树的Prim算法 */ Prim1初始化邻接矩阵 FOR i = 1 TO n DO FOR j = 1 TO n DO IF (edgeij = 0) THEN 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. / 支撑树的边记数器count,Prim3构造图的最小支撑树 FOR i =2

20、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./ 计数器加

21、1 Lowcost (closedgev) 0. / 修改域值 Vex(closedgev) -1./ 顶点v进入集合U / 修改v的邻接顶点的closedge值 FOR j = 1 TO n DO IF(Vex(closedgej) -1 AND edgevj Lowcost(closedgej) THEN ( Lowcost(closedgej) edgevj . Vex(closedgej) v. ) ) ) 普里姆算法的时间复杂度为O(n2) ，适用于求边稠密网的最小支撑树。,普里姆算法图示： 算法Prim2部分 Prim2以顶点1为初始顶点，初始化数组closedge FOR i =

22、 1 TO n DO ( Lowcost (closedgei)edge1i . Vex (closedgei) 1) Vex (closedge1) -1./ 顶点1进入集合U count 1. / 支撑树的边记数器count,算法Prim3第1部分 Prim3构造图的最小支撑树 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 (clo

23、sedgej) . ),算法Prim3第2部分 IF v0 THEN /将该边加入TE中，点v加入集合U中 ( head(TEcount) Vex (closedgev) . tail (TEcount) v. cost (TEcount) Lowcost(closedgev) . count count +1. / 计数器加1 Lowcost (closedgev) 0. / 修改域值 Vex(closedgev) -1. / 顶点v进入集合U,算法Prim3第3部分 / 修改v的邻接顶点的closedge值 FOR j = 1 TO n DO IF(Vex(closedgej) -1 AN

24、D edgevj Lowcost(closedgej) THEN ( Lowcost(closedgej) edgevj . Vex(closedgej) v. ) ) ),算法Prim3第1部分 Prim3构造图的最小支撑树 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) . ),算法Prim3第2部分 IF v

25、0 THEN /将该边加入TE中，点v加入集合U中 ( head(TEcount) Vex (closedgev) . tail (TEcount) v. cost (TEcount) Lowcost(closedgev) . count count +1. / 计数器加1 Lowcost (closedgev) 0. / 修改域值 Vex(closedgev) -1. / 顶点v进入集合U,算法Prim3第3部分 / 修改v的邻接顶点的closedge值 FOR j = 1 TO n DO IF(Vex(closedgej) -1 AND edgevj Lowcost(closedgej)

26、THEN ( Lowcost(closedgej) edgevj . Vex(closedgej) v. ) ) ),算法Prim3第1部分 Prim3构造图的最小支撑树 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) . ),算法Prim3第2部分 IF v0 THEN /将该边加入TE中，点v加入集合U中 (

27、head(TEcount) Vex (closedgev) . tail (TEcount) v. cost (TEcount) Lowcost(closedgev) . count count +1. / 计数器加1 Lowcost (closedgev) 0. / 修改域值 Vex(closedgev) -1. / 顶点v进入集合U,算法Prim3第3部分 / 修改v的邻接顶点的closedge值 FOR j = 1 TO n DO IF(Vex(closedgej) -1 AND edgevj Lowcost(closedgej) THEN ( Lowcost(closedgej) ed

28、gevj . Vex(closedgej) v. ) ) ),算法Prim3第1部分 Prim3构造图的最小支撑树 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) . ),算法Prim3第2部分 IF v0 THEN /将该边加入TE中，点v加入集合U中 ( head(TEcount) Vex (closedgev) . tail (TEcount) v. cost (TEcount) Lowcost(closedgev) . count count +1. / 计数器加1 Lowcost (closedgev) 0. / 修改域值 Vex(closedgev) -1. / 顶点v进入集合U,算法Prim3第3部分 / 修改v的邻接顶点的closedge值 FOR j = 1 TO n DO IF(Vex(closedgej) -1 AND edgevj Lowcost(closedgej) THEN