搜索
6.4图的生成树和最小生成树三大要素三大要素(1)n个顶点(2)n−1条边(3)没有回路生成树——是无向连通图G的某个连通子图〖Example〗某无向连通图G及其生成树最小生成树生成树代价生成树代价对图中每条边赋于一个权值（代价），则构成一个网，对图中每条边赋于一个权值（代价），则构成一个网，网的生成树网的生成树GG’’=(V.{T})=(V.{T})的的代价代价是是TT中各边的权值之和，中各边的权值之和，最小生成树就是网上所有可能的生成树中，最小生成树就是网上所有可能的生成树中，代价最小的一类生成树。代价最小的一类生成树。最小生成树也不一定唯一。最小生成树也不一定唯一。【说明】1.dfsandbfs形成不同的生成树021302133.生成树是最小子图。即：G’⊂G并且V(G’)=V(G),G’是连通的,E(G’)是E(G)的最小集2.如果在生成树上再增加任一条边，将形成回路cycle.普里姆（普里姆（PrimPrim））最小生成树算法最小生成树算法设设N=N=（（VV，，{E}{E}））是一个连通网，是一个连通网，V={1V={1，，22，，……，，n}n}是是NN的顶点集合，的顶点集合，辅助集合辅助集合UU，，初值为初值为{{UoUo}}，，用来存放当前所得到的最小生成树的顶点；用来存放当前所得到的最小生成树的顶点；辅助集合辅助集合TETE，，初值为初值为{}{}，，用来存放当前所得到的最小生成树的边。用来存放当前所得到的最小生成树的边。PrimPrim算法步骤算法步骤1.TE=1.TE=ФФ,U={u,U={u00}}2.2.当当UU≠≠VV，，重复下列步骤：重复下列步骤：(1)(1)选取（选取（uu00,v,v00)=min{cost(u,v)|)=min{cost(u,v)|uu∈∈U,vU,v∈∈VV--UU}}，，保证不形成回路保证不形成回路(2)TE=TE+(2)TE=TE+（（uu00,v,v00),),边（边（uu00,v,v00))并入并入TETE(3)U=U+{V(3)U=U+{V00}}，，顶点顶点VV00并入并入UU初始化：①①②②①①④④⑤⑤552211③③33446666555566⑥⑥①①11③③第1步：66①①11③③44第2步：④④66①①11③③4422第3步：55②②④④66①①11③③4422第4步：233⑤⑤②②55④④66①①11③③44第5步：特点特点::以连通为主以连通为主选代价最小的邻接边选代价最小的邻接边VClosedge123456UV-UTEVEXLOWCOST0①6①①11①①55①①∞①①∞{1}{2,3,4,5,6}{}0③③550①①55③③66③③44{1,3}{2,4,5,6}{1,3}0③③550⑥2③③660{1,3,6}{2,4,5}..(3,6)0③③5500③③660{1,3,6,4}{2,5}..(6,4)0000②30{1,3,6,4,2}{5}..(3,2)000000{1,3,6,4,2,5}{}..(2.5)②②①①④④⑤⑤552211③③33446666555566⑥⑥【例子】克鲁斯卡尔（克鲁斯卡尔（KruskalKruskal））最小生成树算法最小生成树算法KruskalKruskal算法是逐步给生成树算法是逐步给生成树TT中添加不和中添加不和TT中的边构成回路中的边构成回路的当前最小代价边。的当前最小代价边。特点特点::以最小代价边主以最小代价边主设设N=N=（（VV，，{E}{E}））是个连通网是个连通网,,算法步骤为：算法步骤为：1.1.置生成树置生成树TT的初始状态为的初始状态为T=T=（（VV，，{{ФФ}}））2.2.当当TT中边数中边数nn--11时时,,重复下列步骤重复下列步骤::••从从EE中选取代价最小的边（中选取代价最小的边（v,uv,u））,,并删除之并删除之;;••若（若（v,uv,u））依附的顶点依附的顶点vv和和uu落在落在TT中不同的连同分量上，中不同的连同分量上，则将边（则将边（v,uv,u））并入到并入到TT的边集中；的边集中；否则，舍去该边，选择下一条代价最小的边否则，舍去该边，选择下一条代价最小的边..②②①①④④⑤⑤552211③③33446666555566⑥⑥②②①①④④⑤⑤5522③③33446666555566⑥⑥②②①①④④⑤⑤③③⑥⑥②②①①④④⑤⑤③③⑥⑥1(1,3)1(1,3)00步骤步骤(v,u)E(v,u)ETT②②①①④④⑤⑤55③③33446666555566⑥⑥步骤步骤(v,u)E(v,u)ETT3(2,5)3(2,5)2(4,6)2(4,6)②②①①④④⑤⑤③③⑥⑥②②①①④④⑤⑤55③③446666555566⑥⑥②②①①④④⑤⑤③③⑥⑥5(1,4)5(1,4)4(3,6)4(3,6)②②①①④④⑤⑤55③③6666555566⑥⑥②②①①④④⑤⑤③③6666555566⑥⑥②②①①④④⑤⑤③③⑥⑥②②①①④④⑤⑤③③⑥⑥步骤步骤(v,u)E(v,u)ETT步骤步骤(v,u)E(v,u)ETT6(2,3)6(2,3)②②①①④④⑤⑤③③66665566⑥⑥②②①①④④⑤⑤③③⑥⑥边数边数=n=n--1=51=5代价代价=15=156.56.5最短路径（最短路径（ShortestPaths）在有向图中，寻找从某个源点到其余各个顶点或者每一对顶点之间的最短带权路径的运算，称为最短路径问题1.某个源点到其余各顶点的最短路径算法某个源点到其余各顶点的最短路径算法迪杰特拉（迪杰特拉（DijkstraDijkstra））算法：算法：v0v1v2v3v4v52010501515201035303453)v0v2v3v12)v0v2v34)v0v41)v0v2PathLength10254545II算法思想：按路径长度递增的次序产生到各顶点的最短路径算法思想：按路径长度递增的次序产生到各顶点的最短路径II使用使用DSDS：：••利用带权邻接矩阵利用带权邻接矩阵costcost••表示当前找到的从源点表示当前找到的从源点V0V0到每个终点到每个终点VVii的最短路径长度的辅助向量的最短路径长度的辅助向量dist[i]dist[i]••存储最短路径的向量存储最短路径的向量path[i]path[i]••表示已找到从表示已找到从V0V0出发的最短路径的终点的集合出发的最短路径的终点的集合SSII算法步骤：算法步骤：1.1.用用costcost初始化初始化distdist；置；置S={V0}S={V0}；；2.2.选择选择VVjj,,使得：使得：dist[j]=Min{dist[i]|Vdist[j]=Min{dist[i]|Vii∈∈VV--S}S}VVjj就是当前求得的从就是当前求得的从V0V0出发的最出发的最短路径的终点，并将短路径的终点，并将VVjj并入并入SS；；3.3.对对VV--SS上的所有顶点上的所有顶点VVkk，，修改：修改：dist[k]=Min{dist[j]+cost[j,k],dist[k]}dist[k]=Min{dist[j]+cost[j,k],dist[k]}4.4.重复重复22，，33，，nn--11次。次。举例说明举例说明v0v5v2v4v310100605030v152010cost012345∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞105∞∞∞∞∞∞∞502030∞∞∞∞1001060∞012345终点终点从从vv00到各终点的到各终点的distdist值和最短路径值和最短路径v1v2v4v3v5vjv5v3v2v410(v0,v2)30(v0,v4)100(v0,v5)∞∞∞∞60(v0,v2,v3)30(v0,v4)100(v0,v5)∞∞50(v0,v4,v3)90(v0,v4,v5)∞∞60(v0,v4,v3,v5)∞∞∞∞•时间复杂度O（n2）2.每一对顶点之间的最短路径每一对顶点之间的最短路径Method1每次以一个顶点为源点，重复调用每次以一个顶点为源点，重复调用DijkstraDijkstra算法算法nn次；次；Method2弗洛伊德算法弗洛伊德算法((FloyedFloyed))弗洛伊德算法思想：以弗洛伊德算法思想：以AA(0)(0)[i,j]=cost[i,j][i,j]=cost[i,j]递推出：递推出：其中，其中，AA[k][k][i,j][i,j]表示从表示从vvii到到vvjj的中间顶点的序号不大于的中间顶点的序号不大于kk的最短路径长度。最的最短路径长度。最后得到的后得到的A[n][i,j]就是从就是从vvii到到vvjj的最短路径长度的最短路径长度。。0]},][[]][[],][[min{]][[111≥+=−−−kjkAkiAjiAjiAkkkk（（vivivjvj))A-1(viv0(viv0vjvj))A0判断（判断（viv0)(v0viv0)(v0vjvj))是否存在，比较路径长度是否存在，比较路径长度(viv0v1(viv0v1vjvj))A1………………(vi(vi……vkvk……vjvj))Ak……………………（（vivi……vnvn--11……vjvj))An-1(vi(vivjvj))的的最短路径最短路径A(-1)A(0)A(1)A(2)A(3)01230123012301230123001∞401∞4011030110301931∞092∞092∞09212092110822350834073406340634063∞∞60∞∞60∞∞609106091060Path(-1)Path(0)Path(1)Path(2)Path(3)01230123012301230123000000000001100110031100110011001120112031222022000200120012001300300030003020302030••以以PathPath(3)(3)为例，对最短路径的读法加以为例，对最短路径的读法加以说明。说明。从从AA(3)(3)知，顶点知，顶点11到到00的最短路径的最短路径长度为长度为distdist[1][0]=11,[1][0]=11,••其最短路径看其最短路径看pathpath[1][[1][00]=]=22，，pathpath[1][[1][22]]==33，，pathpath[1][[1][33]=]=11,,表示顶点表示顶点00←←顶点顶点22←←顶点顶点33←←顶点顶点1;1;从顶点从顶点11到顶点到顶点00最短最短路径为路径为1,3,3,2,2,01,3,3,2,2,0for(i=0;iCurrentVtxNum;i++)//输出路径长度及路径for(j=1;jCurrentVtxNum;j++){if(i!=j){coutdist[i][j]“:”;intnext=path[i][j];coutj;while(next!=i){cout“←”next;next=path[i][next];}cout“←”iendl;}}}•时间复杂度O（n3）6.6有向无环图及其应用•6.6.1、有向无环图•有向无环图（简称为DAG图）是指无环的有向图，它是一类比有向树更一般的特殊有向图。如图DAG图和有向图的例子。（c）有向图（b）DAG图6.6.26.6.2拓扑排序拓扑排序((topologicalsort)topologicalsort)拓扑排序是一种对非线性结构的有向图进行线性化的重要手段拓扑排序是一种对非线性结构的有向图进行线性化的重要手段•有向无环图常用于描述任务安排问题。一般地说，一个较大的工程往往被划分成许多子工程，这些子工程称为活动(Activity)，这些子工程之间通常受到一定条件的约束，但有些子工程没有先决条件。只有这些子工程都顺利完成后，整个工程才能完成。•例如，一件设备的生产过程包含着许多工序；一个教学计划包含许多课程等等。在每个计划包含的许多活动之间，各种计划的执