最小生成树算法详解课件.ppt
A,1,最小生成树算法-prim& Kruskal,A,2,生成树的概念,生成树一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。生成树不唯一,生成树,A,3,最小代价生成树,生成树的代价等于其边上的权值之和。,V4,V1,V3,V2,V6,V5,6,5,1,2,6,6,5,5,3,4,A,4,最小代价生成树,两种常用的构造最小生成树的方法：普里姆算法（prim）克鲁斯卡尔算法（ Kruskal）,A,5,普里姆(Prim)算法,假设N=(V，E)是连通网，TE是N上最小生成树中边的集合。算法从U=u0(u0V)，TE=开始，重复执行下述操作：在所有uU，vV-U的边(u，v)中找一条代价最小的边(u0 ,v0),将其并入集合TE，同时将v0并入U集合。当U=V则结束，此时TE中必有n-1条边，则T=(V，TE)为N的最小生成树。普里姆算法构造最小生成树的过程是从一个顶点U=u0作初态，不断寻找与U中顶点相邻且代价最小的边的另一个顶点，扩充到U集合直至U=V为止。,A,6,V4,V1,V3,V2,V6,V5,6,5,1,2,6,6,5,5,3,4,V4,V1,V3,V2,V6,V5,1,2,5,3,4,U,V-U,V1 , V2 ,V3 ,V4 , V5 ,V6 ,步骤,(0),最小代价生成树,普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止,A,7,V4,V1,V3,V2,V6,V5,1,6,5,V1,V3,1,V1 , V2 ,V3 ,V4 , V5 ,V6 ,步骤,(0),U,V-U,普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止,最小代价生成树,A,8,V4,V1,V3,V2,V6,V5,6,5,V1,V3,1,V1 , V2 ,V3 ,V4 , V5 ,V6 ,步骤,(0),V6,4,6,5,5,4,U,V-U,普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止,最小代价生成树,A,9,V4,V1,V3,V2,V6,V5,6,5,V4,V1,V3,1,V1 , V2 ,V3 ,V4 , V5 ,V6 ,步骤,(0),V6,4,6,5,5,2,6,2,U,V-U,普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止,最小代价生成树,A,10,V4,V1,V3,V2,V6,V5,6,V4,V1,V3,1,V1 , V2 ,V3 ,V4 , V5 ,V6 ,步骤,(0),V2,V6,4,6,5,6,2,5,U,V-U,普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止,最小代价生成树,A,11,V4,V1,V3,V2,V6,V5,V4,V1,V3,1,V1 , V2 ,V3 ,V4 , V5 ,V6 ,步骤,(0),V2,V6,V5,4,6,6,2,5,3,3,U,V-U,普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止,最小代价生成树,A,12,普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止,V4,V1,V3,V2,V6,V5,V4,V1,V3,1,V1 , V2 ,V3 ,V4 , V5 ,V6 ,步骤,(0),V2,V6,V5,4,2,5,3,U,V-U,最小代价生成树,A,13,普里姆(Prim)算法,生成树中只放置一个顶点,在关联生成树顶点的边中（即边的一个顶点在生成树中，另一个顶点不在）取权值最小者,将选中的边加入生成树，同时将该边的关联顶点加入生成树中,生成树中顶点数小于n?,是,否,结束,开始,A,14,从键盘（或数据文件）输入图的信息，用普里姆算法求解给定无向连通图的最小生成树，最后输出最小生成树中的权值和所有的边，图的存储结构自行设定。,基本要求,例如 下图的输出为,weight：15(v1, v3) (v3, v6) (v6, v4) (v3, v2) (v2, v5)或者(1, 3) (3, 6) (6, 4) (3, 2) (2, 5),A,15,普里姆算法的实现,顶点集合如何表示？最小边如何选择？一个顶点加入U集合（生成树中） 如何表示？,struct int adjvex; double lowcost;closedgeMAX_VERTEX_NUM;,closedgei.adjvex=k,closedgei.lowcost,顶点i与顶点k邻接顶点k已经在U集合中,顶点i加入U集合时,= 0,A,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集合的成员：,closedge5.adjvex=1 .lowcost=,closedge6.adjvex=1 .lowcost=,A,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,A,18,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,A,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,A,20,V4,V1,V3,V2,V6,V5,3,当U集合中加入一个新顶点时，V-U集合中的顶点到U的最小代价边可能会更新,U集合的成员：,V-U集合的成员：,A,21,V4,V1,V3,V2,V6,V5,U集合的成员：,V-U集合的成员：,A,22,图采用邻接矩阵表示,普里姆算法求最小生成树, 6 1 5 6 5 3 1 5 5 6 4 5 5 2 3 6 6 4 2 6 ,123456,1 2 3 4 5 6,graph. arac =,A,23,#include#include#include#define INIT 63355#define NUM 20using namespace std;typedef int Elemtype;typedef struct Tnode Elemtype vexNUM; int aracNUMNUM; int v,e;graph;void Init_Graph(graph ,void Create_Graph(graph ,A,24,void Prim(graph ,min_cost+=min; coutjendl; /输出符合最小生成树的顶点 sj = 1; /已访问顶点置1 for(int t = 2;t=g.v;t+) if(g.aracjtlowcostt,A,25,Kruskal最小生成树,Kruskal算法步骤：,a.带权图,此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。1. 把图中的所有边按代价（权值）从小到大排序；2.将图中的所有边都去掉。 3.将边按权值从小到大的顺序添加到图中，保证添加的过程中不会形成环（用并查集检测 ）4. 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。,A,26,1,Kruskal最小生成树,5、算法过程示意：,原始图,5,6,4,2,3,1,6,5,3,4,6,5,2,6,5,A,27,1,经典应用最小生成树,5、算法过程示意：,原始图,5,6,4,2,3,1,6,5,3,4,6,5,2,6,5,A,28,1,经典应用最小生成树,5、算法过程示意：,原始图,5,6,4,2,3,1,6,5,3,4,6,5,2,6,5,A,29,1,经典应用最小生成树,5、算法过程示意：,原始图,5,6,4,2,3,1,6,5,3,4,6,5,2,6,5,A,30,1,经典应用最小生成树,5、算法过程示意：,原始图,5,6,4,2,3,1,6,5,3,4,6,5,2,6,5,34这条边（蓝色表示）加入会形成环，所以这条边不能用,A,31,1,经典应用最小生成树,5、算法过程示意：,原始图,5,6,4,2,3,1,6,5,3,4,6,5,2,6,5,14这条边（蓝色表示）加入会形成环，所以这条边不能用,A,32,1,经典应用最小生成树,5、算法过程示意：,原始图,5,6,4,2,3,1,6,5,3,4,6,5,2,6,5,A,33,1,经典应用最小生成树,5、算法过程示意：,原始图,5,6,4,2,3,1,5,3,4,2,最小生成树,A,34,克鲁斯卡尔(Kruskal)算法,否,将当前这条边加入生成树后是否形成回路?,在生成树中放置n个孤立顶点（即并查集里顶点的初始化）,根据边上的权值从小到大排序,是,将该边加入生成树中,继续选择下一条边,生成树中边数小于n-1?,是,否,结束,开始,A,35,代码参考,
