最小生成树算法详解.ppt

1、b,1,最小生成树算法 -prim double lowcost; closedgeMAX_VERTEX_NUM;,closedgei.adjvex=k,closedgei.lowcost,顶点i与顶点k邻接 顶点k已经在U集合中,顶点i加入U集合时,= 0,b,16,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集合的

2、成员：,closedge5.adjvex=1 .lowcost=,closedge6.adjvex=1 .lowcost=,b,17,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,b,18,V4,V1,V3,V2,V6,V5,5,6,2,当U集

3、合中加入一个新顶点时，V-U集合中的顶点到U的最小代价边可能会更新,U集合的成员：,V-U集合的成员：,closedge2.adjvex=3 .lowcost=5,closedge4.adjvex=6 .lowcost=2,closedge5.adjvex=3 .lowcost=6,b,19,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,b,20,V4,V1,V3,V2

4、,V6,V5,3,当U集合中加入一个新顶点时，V-U集合中的顶点到U的最小代价边可能会更新,U集合的成员：,V-U集合的成员：,b,21,V4,V1,V3,V2,V6,V5,U集合的成员：,V-U集合的成员：,b,22,图采用邻接矩阵表示,普里姆算法求最小生成树, 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 =,b,23,#include #include #include #define INIT 63355 #define NUM 20 using namespace std; t

5、ypedef int Elemtype; typedef struct Tnode Elemtype vexNUM; int aracNUMNUM; int v,e; graph; void Init_Graph(graph ,void Create_Graph(graph ,b,24,void Prim(graph ,min_cost+=min; coutjendl; /输出符合最小生成树的顶点 sj = 1; /已访问顶点置1 for(int t = 2;t=g.v;t+) if(g.aracjtlowcostt ,b,25,Kruskal最小生成树,Kruskal算法步骤：,a.带权图,

6、此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。 1. 把图中的所有边按代价（权值）从小到大排序； 2.将图中的所有边都去掉。 3.将边按权值从小到大的顺序添加到图中，保证添加的过程中不会形成环 （用并查集检测 ） 4. 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。,b,26,1,Kruskal最小生成树,5、算法过程示意：,原始图,5,6,4,2,3,1,6,5,3,4,6,5,2,6,5,b,27,1,经典应用最小生成树,5、算法过程示意：,原始图,5,6,4,2,3,1,6,5,3,4,6,5,2,6,

7、5,b,28,1,经典应用最小生成树,5、算法过程示意：,原始图,5,6,4,2,3,1,6,5,3,4,6,5,2,6,5,b,29,1,经典应用最小生成树,5、算法过程示意：,原始图,5,6,4,2,3,1,6,5,3,4,6,5,2,6,5,b,30,1,经典应用最小生成树,5、算法过程示意：,原始图,5,6,4,2,3,1,6,5,3,4,6,5,2,6,5,34这条边（蓝色表示）加入会形成环，所以这条边不能用,b,31,1,经典应用最小生成树,5、算法过程示意：,原始图,5,6,4,2,3,1,6,5,3,4,6,5,2,6,5,14这条边（蓝色表示）加入会形成环，所以这条边不能用,b,32,1,经典应用最小生成树,5、算法过程示意：,原始图,5,6,4,2,3,1,6,5,3,4,6,5,2,6,5,b,33,1,经典应用最小生成树,5、算法过程示意：,原始图,5,6,4,2,3,1,5,3,4,2,最小生成树,b,34,克鲁斯卡尔(Kruskal)算法,否