给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树.
求最小生成树的算法 (1) 克鲁斯卡尔算法 图的存贮结构采用边集数组,且权值相等的边在数组中排列次序可以是任意的.该方法对于边相对比较多的不是很实用,浪费时间. (2) 普里姆算法 图的存贮结构采用邻接矩阵.此方法是按各个顶点连通的步骤进行,需要用一个顶点集合,开始为空集,以后将以连通的顶点陆续加入到集合中,全部顶点加入集合后就得到所需的最小生成树 .
下面来具体讲下： 克鲁斯卡尔算法 方法:将图中边按其权值由小到大的次序顺序选取,若选边后不形成回路,则保留作为一条边,若形成回路则除去.依次选够(n-1)条边,即得最小生成树.(n为顶点数) 第一步:由边集数组选第一条边 第二步:选第二条边,即权值为2的边 第三步:选第三条边,即权值为3的边 第四步:选第四条边,即权值为4的边 第五步:选第五条边
这也是在网上找到的一个Kruskal构造过程图，贴出来： typedef struct { char vertex[VertexNum]; //顶点表 int edges[VertexNum][VertexNum]; //邻接矩阵,可看做边表 int n,e; //图中当前的顶点数和边数 }MGraph; typedef struct node { int u; //边的起始顶点 int v; //边的终止顶点 int w; //边的权值 }Edge; void kruskal(MGraph G) { int i,j,u1,v1,sn1,sn2,k; int vset[VertexNum]; //辅助数组，判定两个顶点是否连通 int E[EdgeNum]; //存放所有的边 k=0; //E数组的下标从0开始 for (i=0;i<G.n;i++) { for (j=0;j<G.n;j++) { if (G.edges[i][j]!=0 && G.edges[i][j]!=INF) { E[k].u=i; E[k].v=j; E[k].w=G.edges[i][j]; k++; } } } heapsort(E,k,sizeof(E[0])); //堆排序，按权值从小到大排列 for (i=0;i<G.n;i++) //初始化辅助数组 { vset[i]=i; } k=1; //生成的边数，最后要刚好为总边数 j=0; //E中的下标 while (k<G.n) { sn1=vset[E[j].u]; sn2=vset[E[j].v]; //得到两顶点属于的集合编号 if (sn1!=sn2) //不在同一集合编号内的话，把边加入最小生成树 { printf("%d ---> %d, %d",E[j].u,E[j].v,E[j].w); k++; for (i=0;i<G.n;i++) { if (vset[i]==sn2) { vset[i]=sn1; } } } j++; } }
普里姆算法 方法:从指定顶点开始将它加入集合中,然后将集合内的顶点与集合外的顶点所构成的所有边中选取权值最小的一条边作为生成树的边,并将集合外的那个顶点加入到集合中,表示该顶点已连通.再用集合内的顶点与集合外的顶点构成的边中找最小的边,并将相应的顶点加入集合中,如此下去直到全部顶点都加入到集合中,即得最小生成树. 例在下图中从1点出发求出此图的最小生成树,并按生成树的边的顺序将顶点与权值填入表中. ———————>先写出其邻接矩阵 第一步:从①开始，①进集合，用与集合外所有顶点能构成的边中找最小权值的一条边 ①——②权6 ①——③权1 -> 取①——③边 ①——④权5
第二步:③进集合，①，③与②,④,⑤,⑥构成的最小边为 ①——④权5 ③——⑥权4 -> 取③——⑥边
第三步:⑥进集合，①，③,⑥与②,④,⑤构成的各最小边 ①——②权6 ③——②权5 ⑥——④权2 -> 取⑥——④边
第四步:④进集合，①，③,⑥,④与②,⑤构成的各最小边 ①——②权6 ③——②权5 -> 取③——②边 ⑥——⑤权6
第四步:②进集合，①，③,⑥,②,④与⑤构成的各最小边 ②——⑤权3 -> 取②——⑤边
这也是在网上找到的Prim构造过程图，贴出来：这也是在网上找到的一个Kruskal和Prim构造过程图，贴出来：
#define MAX 100000 #define VNUM 10+1 //这里没有ID为0的点,so id号范围1~10 int edge[VNUM][VNUM]={/*输入的邻接矩阵*/}; int lowcost[VNUM]={0}; //记录Vnew中每个点到V中邻接点的最短边 int addvnew[VNUM]; //标记某点是否加入Vnew int adjecent[VNUM]={0}; //记录V中与Vnew最邻近的点 void prim(int start) { int sumweight=0; int i,j,k=0; for(i=1;i<VNUM;i++) //顶点是从1开始 { lowcost[i]=edge[start][i]; addvnew[i]=-1; //将所有点至于Vnew之外,V之内，这里只要对应的为-1，就表示在Vnew之外 } addvnew[start]=0; //将起始点start加入Vnew adjecent[start]=start; for(i=1;i<VNUM-1;i++) { int min=MAX; int v=-1; for(j=1;j<VNUM;j++) { if(addvnew[j]!=-1&&lowcost[j]<min) //在Vnew之外寻找最短路径 { min=lowcost[j]; v=j; } } if(v!=-1) { printf("%d %d %d\n",adjecent[v],v,lowcost[v]); addvnew[v]=0; //将v加Vnew中 sumweight+=lowcost[v]; //计算路径长度之和 for(j=1;j<VNUM;j++) { if(addvnew[j]==-1&&edge[v][j]<lowcost[j]) { lowcost[j]=edge[v][j]; //此时v点加入Vnew 需要更新lowcost adjecent[j]=v; } } } } printf("the minmum weight is %d",sumweight); }