数据结构课件：第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中其它顶点的最短路径, 限定各边的权值为正实数。v0v1v2283 Dijkstra算法思想 按路

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

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

4、thdist100010342103028311v0v0v1v13258133002343028111325810204530120234 03421spathdist1100103028311v0 v1v1 v013258102045301202343120415813234231103421spathdist1100102315311v0v3v1v3132581020453012023431204158132342311120415813234231131325810204530120234spathdist1101102315311v0v3v1v3spathdist11111034210

5、2315311v0v3v1v3Dijkstra算法: 按照非递减顺序依次得到各顶点的最小路径长度。120415813234231131325810204530120234正权单源最短路径问题的 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为即将访问的顶点1325810204530120234 DSPa

6、th1初始化 FOR i = 1 TO n DO ( pathi-1. disti max. si 0. ) distv 0. sv 1. p adjacent (Headv) . u v. / u为即将访问的顶点11111spathdisk000000342111111spathdist10000034210012340243105134303822541002024412p1325810204530120234 DSPath2求从初始顶点v到其他各顶点的最短路径 算法DSPath2第1部分 FOR j = 1 TO n-1 DO / 求从v到其他各顶点的最短路径 (WHILE p DO /

7、修改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) ) spathdist10000034210303v0,v1v0,v4spathdist10001034210303v0,v1v0,v4325813300234302811 算法DSPath2第1部分 FOR j = 1 TO n-1 DO / 求从v到其他各顶点的最短路径 (WHILE p

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

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

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

11、p adjacent (Headu) ) spathdist111110342102315311v0,v1v0v1v3v2v0v1v3v0v1v3v41201581323423113 spathdist111110342102315311v0,v1v0v1v3v2v0v1v3v0v1v3v41325810204530120234该算法的时间复杂性为O(n2+e)，也可认为是O(n2) 412015813234231135.6.3 每对顶点间的最短路径问题：已知一个各边权值均大于0的带权有向图，对每一对顶点 vi vj，求vi 与vj间的最短路径和最短路径长度。可依次把每个顶点作为源点，执行n次

12、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的最短路径长度； 经过n次运算后，最后求得的就是从vi-vj的最短路径。 其中 A(k) ij = min A(k-1)ij， A(k-1)ik + A(k-1)kj , k = 0,

13、1, n-1 例 求下图中每对顶点之间的最短路径。0123 0 1 4 0 9 2 3 5 0 8 6 00 1 2 3A（1） 230139821654 A(k)ij = minA(k-1)ij,A(k-1)ik+ A(k-1)kj|0 k n-1当i=j时，公式变为：A(k)ij = minA(k-1)ii,A(k-1)ik+ A(k-1)ki|0 k n-1= 00123 0 1 4 0 9 2 3 5 0 8 6 00 1 2 3A（1） 0123 0 1 4 0 9 2 3 4 0 7 6 00 1 2 3A（0） A(k)ij = minA(k-1)ij,A(k-1)ik+ A(k

14、-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-1A(k)ik = minA(k-1)ik,A(k-1)ik+ A(k-1)kk | 0 k n-10123 0 1 4 0 9 2 3 5 0 8 6 00 1 2 3A（1）A（0）0123 0 1 4 0 9 2 3 4 0 7 6 00 1 2 3 2301398216540123 0 1 4 0 9 2 3 5 0 8 6 00 1 2 3A（1） 0123 0 1 4 0 9 2 3 4 0 7 6 00 1 2 3A（0） A(k

15、)ij = minA(k-1)ij,A(k-1)ik+ A(k-1)kj|0 k n-1 2301398216540123 0 1 4 0 9 2 3 4 0 7 6 00 1 2 3A（0） A(k)ij = minA(k-1)ij,A(k-1)ik+ A(k-1)kj|0 k n-10123 0 1 10 3 0 9 2 3 4 0 6 6 00 1 2 3A（1） 230139821654A(k)ij = minA(k-1)ij,A(k-1)ik+ A(k-1)kj|0 k n-10123 0 1 10 3 0 9 2 3 4 0 6 6 00 1 2 3A（1） 0123 0 1 10

16、 3 12 0 9 2 3 4 0 6 9 10 6 00 1 2 3A（2） 230139821654A(k)ij = minA(k-1)ij,A(k-1)ik+ A(k-1)kj|0 k n-10123 0 1 10 3 12 0 9 2 3 4 0 6 9 10 6 00 1 2 3A（2） 0123 0 1 9 3 11 0 8 2 3 4 0 6 9 10 6 00 1 2 3A（3） 求每对顶点之间的最短路径算法 template void Graph:allLength(const int n) for ( int i = 0; i n; i+ ) /矩阵A与path初始化 fo

17、r ( int j = 0; j n; j+ ) Aij = Edgeij; if ( i j & Aij MAXINT ) pathij = i; / i 到 j 有路径 else pathij = 0; / i 到 j 无路径 for ( int k = 0; k n; k+ ) /产生A(k)及path(k) for ( i = 0; i n; i+ ) for ( j = 0; j n; j+ ) if ( Aik + Akj Aij ) Aij = Aik + Akj; pathij = pathkj; /缩短路径长度, 绕过 k 到 j for ( int i = 0; i n;

18、i+ ) /矩阵A与path初始化 for ( int j = 0; j n; j+ ) Aij = Edgeij; if ( i j & Aij MAXINT ) pathij = i; / i 到 j 有路径 else pathij = 0; / i 到 j 无路径 0123 0 1 4 0 9 2 3 5 0 8 6 00 1 2 3A（1） 230139821654 for ( int i = 0; i n; i+ ) /矩阵A与path初始化 for ( int j = 0; j n; j+ ) Aij = Edgeij; if ( i j & Aij MAXINT ) pathij

19、 = i; / i 到 j 有路径 else pathij = 0; / i 到 j 无路径 230139821654path（1）0123 0 0 0 0 0 0 1 1 2 2 0 2 0 0 3 00 1 2 3 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; 0123 0 1 4 0 9 2 3 4 0 7 6 00 1 2 3A（0）=230139821654path（0）0123

20、 0 0 0 0 0 0 1 1 2 0 0 0 0 0 3 00 1 2 3 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; path（1）0123 0 0 1 1 0 0 1 1 2 0 0 1 0 0 3 00 1 2 30123 0 1 10 3 0 9 2 3 4 0 6 6 00 1 2 3A（1） =230139821654 for ( int k = 0; k n; k+ )

21、 for ( i = 0; i n; i+ )for ( j = 0; j n; j+ ) if ( Aik + Akj Aij ) Aij = Aik + Akj; pathij = pathkj; path（2）0123 0 0 1 1 2 0 1 1 2 0 0 1 2 0 3 00 1 2 32301398216540123 0 1 10 3 12 0 9 2 3 4 0 6 9 10 6 00 1 2 3A（2）= for ( int k = 0; k n; k+ ) for ( i = 0; i n; i+ )for ( j = 0; j n; j+ ) if ( Aik + Ak

22、j Aij ) Aij = Aik + Akj; pathij = pathkj; 2301398216540123 0 1 9 3 11 0 8 2 3 4 0 6 9 10 6 00 1 2 3A（3） =path（3）0123 0 0 3 1 2 0 3 1 2 0 0 1 2 0 3 00 1 2 3从A(3)知，顶点1到0的最短路径长度为A10 = 11,其最短路径看 path10 = 2，path12 = 3，path 13 = 1, 表示顶点0 顶点2 顶点3 顶点1;从顶点1到顶点0最短路径为,。 0 Floyd算法的时间复杂度为O(n3)，与调用n次Dijkstra算法求每对

23、顶点的最短路径的时间复杂度相同。 但Dijkstra算法仅针对正权图，而Floyd算法允许图中有带负权值的边，但不许有包含带负权值的边组成的回路；且Floyd算法更简单易于理解。 本章给出的求解最短路径的算法，不仅适用于带权有向图，对带权无向图也可以适用。因为带权无向图可以看作是有往返二重边的有向图。 第五章 图5.1 基本概念5.2 图的存储结构5.3 图的遍历5.4 拓扑排序5.5 关键路径 5.6 最短路径5.7 最小支撑树 5.7 最小支撑树1、基本概念2、生成最小支撑树算法 Prim算法 Kruskar算法最小支撑树基本概念 对于一个无向网络无向加权连通图N=(V,E,C)(C表示该

24、图为权图)，其顶点个数为|V|=n，图中边的个数为|E| ，我们可以从它的|E|条边中选出n-1条边，使之满足 （1）这n-1条边和图的n个顶点构成一个连通图。 （2）该连通图的代价是所有满足条件(1)的连通图的代价的最小值。 这样的连通图被称为网络的最小支撑树( Minimum-cost Spanning Tree )。 最小支撑树的性质最小支撑树中没有回路 若MST 的边集中有回路，显然可通过去掉回路中某条边而得到花销更小的MST最小支撑树是一棵有|V| - 1条边的树最小支撑树的边集支撑起了图中所有顶点，且边集的代价最小最小支撑树的应用使连接电路板上一系列接头所需焊接的线路最短在n个城市

25、间建立造价最低的通讯网络 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。 反复执行 ,直至 V=U 时终止算法。 431650453556221743165045355622170214316504535562217021402154316504535562217021402

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

27、终点和权值。 普里姆算法/* 利用普里姆算法从顶点v1出发求出用邻接矩阵Edge表示的图的最小支撑树，最小支撑树的边集存于数组TE中*/算法Prim( )/* 构造最小支撑树的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 (closed

28、ge1) -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 (TE

29、count) v. cost (TEcount) Lowcost(closedgev) . count count +1./ 计数器加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) ，适用于求边

30、稠密网的最小支撑树。普里姆算法图示：算法Prim2部分Prim2以顶点1为初始顶点，初始化数组closedge FOR i = 1 TO n DO ( Lowcost (closedgei)edge1i . Vex (closedgei) 1) Vex (closedge1) -1./ 顶点1进入集合U count 1. / 支撑树的边记数器count 4316504535562217closedge0vexLowcost0342100005016050closedge0vexLowcost0342100005016051算法Prim3第1部分Prim3构造图的最小支撑树 FOR i =2 T

31、O 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) . )closedge0vexLowcost03421000050160514316504535562217021 算法Prim3第2部分 IF v0 THEN /将该边加入TE中，点v加入集合U中 ( head(TEcount) Vex (closedgev) . tail (TEco

32、unt) v. cost (TEcount) Lowcost(closedgev) . count count +1. / 计数器加1 Lowcost (closedgev) 0. / 修改域值 Vex(closedgev) -1. / 顶点v进入集合UTE0headtail034210000020000050cost000001vexLowcostclosedge003421100050060510214316504535562217closedge0vexLowcost0342100005016051 算法Prim3第3部分 / 修改v的邻接顶点的closedge值 FOR j = 1 T

33、O n DO IF(Vex(closedgej) -1 AND edgevj Lowcost(closedgej) THEN ( Lowcost(closedgej) edgevj . Vex(closedgej) v. ) ) )vexLowcostclosedge003421100050060514316504535562217vexLowcostclosedge0034211024505205251vexLowcostclosedge00342110205005051vexLowcostclosedge003421102505205051算法Prim3第1部分Prim3构造图的最小支撑树

34、 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) . )vexLowcostclosedge0034211024505205251vexLowcostclosedge0034211024505205251431650453556221740215算法Prim3第2部分 IF v0 THEN /将该边加入TE中，点v

35、加入集合U中 ( head(TEcount) Vex (closedgev) . tail (TEcount) v. cost (TEcount) Lowcost(closedgev) . count count +1. / 计数器加1 Lowcost (closedgev) 0. / 修改域值 Vex(closedgev) -1. / 顶点v进入集合UTE0headtail034210020020005050cost004001431650453556221740215vexLowcostclosedge0034211020505205151vexLowcostclosedge0034211

36、024505205251算法Prim3第3部分 / 修改v的邻接顶点的closedge值 FOR j = 1 TO n DO IF(Vex(closedgej) -1 AND edgevj Lowcost(closedgej) THEN ( Lowcost(closedgej) edgevj . Vex(closedgej) v. ) ) )4316504535562217vexLowcostclosedge003421102055205151vexLowcostclosedge003421152052205151算法Prim3第1部分Prim3构造图的最小支撑树 FOR i =2 TO n

37、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) . )43165045355622174053221vexLowcostclosedge0034211520502205151算法Prim3第2部分 IF v0 THEN /将该边加入TE中，点v加入集合U中 ( head(TEcount) Vex (closedgev) . tail (TEc

38、ount) v. cost (TEcount) Lowcost(closedgev) . count count +1. / 计数器加1 Lowcost (closedgev) 0. / 修改域值 Vex(closedgev) -1. / 顶点v进入集合UTE0headtail034215020020035050cost204001vexLowcostclosedge003421112050020515143165045355622174053221vexLowcostclosedge0034211520502205151算法Prim3第3部分 / 修改v的邻接顶点的closedge值 FOR

39、 j = 1 TO n DO IF(Vex(closedgej) -1 AND edgevj Lowcost(closedgej) THEN ( Lowcost(closedgej) edgevj . Vex(closedgej) v. ) ) )4316504535562217vexLowcostclosedge0034211120500205151算法Prim3第1部分Prim3构造图的最小支撑树 FOR i =2 TO n DO / 循环n-1次 ( v 0. minmax. / 求当前权值最小的边和该边的终点v FOR j = 1 TO n DO IF (vex (closedgej)

40、 -1 AND Lowcost(closedgej) min ) THEN ( v j. min Lowcost (closedgej) . )vexLowcostclosedge00342111205002051514316504535562217410535221算法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进入集合UTE0headtail034215220021035050cost254001vexLowcostclosedge00342111105002001514316504535562217410535221vexLowcostclosedge0034211120500205151算法Prim3第3部分 / 修改v的邻接顶点的closedge值 F