最小生成树算法详解.ppt
最小生成树算法 ------prim double lowcost; 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集合的成员：,,图采用邻接矩阵表示,普里姆算法求最小生成树,, 6 1 5 6 5 3 1 5 5 6 4 5 5 2 3 6 6 4 2 6 ,,,,,,,1 2 3 4 5 6,1 2 3 4 5 6,graph. arac =,#include #include #include #define INIT 63355 #define NUM 20 using namespace std; typedef int Elemtype; typedef struct Tnode Elemtype vexNUM; int aracNUMNUM; int v,e; graph; void Init_Graph(graph ,void Create_Graph(graph ,void Prim(graph ,min_cost+=min; cout< 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)算法,否,将当前这条边加入生成树后 是否形成回路?,,,,,在生成树中放置n个孤立顶点（即并查集里顶点的初始化）,,根据边上的权值从小到大排序,是,将该边加入生成树中,继续选择下一条边,,,,生成树中边数小于n-1?,,是,,否,,,结束,,,开始,代码参考,。
