最小生成树算法详解.ppt

最小生成树算法-primdoublelowcost;closedgeMAX_VERTEX_NUM;,closedgei.adjvex=k,closedgei.lowcost,顶点i与顶点k邻接顶点k已经在U集合中,顶点i加入U集合时,=0,closedge2.adjvex=1.lowcost=6,closedge3.adjvex=1.lowcost=1,closedge4.adjvex=1.lowcost=5,V4,V1,V3,V2,V6,V5,1,6,5,当U集合中加入一个新顶点时，V-U集合中的顶点到U的最小代价边可能会更新,U集合的成员：,V-U集合的成员：,closedge5.adjvex=1.lowcost=,closedge6.adjvex=1.lowcost=,V4,V1,V3,V2,V6,V5,5,5,6,4,U集合的成员：,V-U集合的成员：,当U集合中加入一个新顶点时，V-U集合中的顶点到U的最小代价边可能会更新,closedge2.adjvex=3.lowcost=5,closedge4.adjvex=1.lowcost=5,closedge5.adjvex=3.lowcost=6,closedge6.adjvex=3.lowcost=4,V4,V1,V3,V2,V6,V5,5,6,2,当U集合中加入一个新顶点时，V-U集合中的顶点到U的最小代价边可能会更新,U集合的成员：,V-U集合的成员：,closedge2.adjvex=3.lowcost=5,closedge4.adjvex=6.lowcost=2,closedge5.adjvex=3.lowcost=6,V4,V1,V3,V2,V6,V5,5,6,当U集合中加入一个新顶点时，V-U集合中的顶点到U的最小代价边可能会更新,U集合的成员：,V-U集合的成员：,closedge2.adjvex=3.lowcost=5,closedge5.adjvex=3.lowcost=6,V4,V1,V3,V2,V6,V5,3,当U集合中加入一个新顶点时，V-U集合中的顶点到U的最小代价边可能会更新,U集合的成员：,V-U集合的成员：,V4,V1,V3,V2,V6,V5,U集合的成员：,V-U集合的成员：,图采用邻接矩阵表示,普里姆算法求最小生成树,61565315564552366426,123456,123456,graph.arac=,#include#include#include#defineINIT63355#defineNUM20usingnamespacestd;typedefintElemtype;typedefstructTnodeElemtypevexNUM;intaracNUMNUM;intv,e;graph;voidInit_Graph(graph,voidCreate_Graph(graph,voidPrim(graph,min_cost+=min;coutjendl;/输出符合最小生成树的顶点sj=1;/已访问顶点置1for(intt=2;t=g.v;t+)if(g.aracjtlowcostt,Kruskal最小生成树,Kruskal算法步骤：,a.带权图,此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。1.把图中的所有边按代价（权值）从小到大排序；2.将图中的所有边都去掉。3.将边按权值从小到大的顺序添加到图中，保证添加的过程中不会形成环（用并查集检测）4.重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。,1,Kruskal最小生成树,5、算法过程示意：,原始图,5,6,4,2,3,1,6,5,3,4,6,5,2,6,5,1,经典应用最小生成树,5、算法过程示意：,原始图,5,6,4,2,3,1,6,5,3,4,6,5,2,6,5,1,经典应用最小生成树,5、算法过程示意：,原始图,5,6,4,2,3,1,6,5,3,4,6,5,2,6,5,1,经典应用最小生成树,5、算法过程示意：,原始图,5,6,4,2,3,1,6,5,3,4,6,5,2,6,5,1,经典应用最小生成树,5、算法过程示意：,原始图,5,6,4,2,3,1,6,5,3,4,6,5,2,6,5,34这条边（蓝色表示）加入会形成环，所以这条边不能用,1,经典应用最小生成树,5、算法过程示意：,原始图,5,6,4,2,3,1,6,5,3,4,6,5,2,6,5,14这条边（蓝色表示）加入会形成环，所以这条边不能用,1,经典应用最小生成树,5、算法过程示意：,原始图,5,6,4,2,3,1,6,5,3,4,6,5,2,6,5,1,经典应用最小生成树,5、算法过程示意：,原始图,5,6,4,2,3,1,5,3,4,2,最小生成树,克鲁斯卡尔(Kruskal)算法,否,将当前