频道栏目
首页 > 资讯 > 其他 > 正文

最小生成树

16-07-15        来源:[db:作者]  
收藏   我要投稿

一个连通图的生成树是一个极小的连通子图,包含图中全部顶点,但只有足以构成一棵树的n-1条边。于是,将构造连通网的最小代价生成树称为最小生成树(Minimum Cost Spanning Tree)。经典的算法有两种,普里姆算法和克鲁斯卡尔算法,下面详细介绍。

普里姆(Prim)算法

/*Prim算法生成最小生成树,邻接矩阵,时间复杂度O(n^2)*/
void MiniSpanTree(MGraph G){
   int min,i,j,k;
   int adjvex[MAXSIZE]; //保存相关顶点下标
   int lowcost[MAXSIZE];  //保存边的权值
   lowcost[0]=0;  //初始化,将v0加入生成树,下标为0的已加入树
   adjvex[0]=0;  //初始化第一个顶点下标为0
   /*读取邻接矩阵第一行数据,并将数组赋值给lowcost数组*/
   for(i=1;i

首先将 v0 加入最小生成树, v0 行的邻接矩阵为 [0,10,∞,∞,∞,11,,∞,∞,∞] ,adjvex全部为0,lowcost等于其邻接矩阵,找到其中的最小值10,对应的顶点为 v1;

将 v1 加入到最小生成树中,并将lowcost和 v1 这行的邻接矩阵进行比较,更小的加入到lowcost中,为0的不参与比较,所以lowcost=[0,0,18,∞,∞,11,16,∞,12] ,adjvex={0,0,1,0,0,0,1,0,1},发现当前的lowcost中的最小值为11,下标为5,对应的顶点为 v5;

将 v5 加入到最小生成树中,并将lowcost和 v5 这行的邻接矩阵进行比较,更小的加入到lowcost中,为0的不参与比较,所以lowcost=[0,0,18,∞,26,0,16,∞,12] ,adjvex={0,0,1,0,5,0,1,0,1},发现当前的lowcost中的最小值为12,下标为8,对应的顶点为 v8;

将 v8 加入到最小生成树中,并将lowcost和 v8 这行的邻接矩阵进行比较,更小的加入到lowcost中,为0的不参与比较,所以lowcost=[0,0,8,21,26,0,16,∞,0] ,adjvex={0,0,8,8,5,0,1,0,1},发现当前的lowcost中的最小值为8,下标为2,对应的顶点为 v2;

将 v2 加入到最小生成树中,并将lowcost和 v2 这行的邻接矩阵进行比较,更小的加入到lowcost中,为0的不参与比较,所以lowcost=[0,0,0,21,26,0,16,∞,0] ,adjvex={0,0,8,8,5,0,1,0,1},发现当前的lowcost中的最小值为16,下标为6,对应的顶点为 v6;

将 v6 加入到最小生成树中,并将lowcost和 v6 这行的邻接矩阵进行比较,更小的加入到lowcost中,为0的不参与比较,所以lowcost=[0,0,0,21,26,0,0,19,0] ,adjvex={0,0,8,8,5,0,1,6,1},发现当前的lowcost中的最小值为19,下标为7,对应的顶点为 v7;

将 v7 加入到最小生成树中,并将lowcost和 v7 这行的邻接矩阵进行比较,更小的加入到lowcost中,为0的不参与比较,所以lowcost=[0,0,0,16,7,0,0,0,0] ,adjvex={0,0,8,7,7,0,1,6,1},发现当前的lowcost中的最小值为7,下标为4,对应的顶点为 v4;

将 v4 加入到最小生成树中,并将lowcost和 v4 这行的邻接矩阵进行比较,更小的加入到lowcost中,为0的不参与比较,所以lowcost=[0,0,0,16,0,0,0,0,0] ,adjvex={0,0,8,7,7,0,1,6,1},发现当前的lowcost中的最小值为16,下标为3,对应的顶点为 v3;

将 v3 加入到最小生成树中,并将lowcost和 v3 这行的邻接矩阵进行比较,更小的加入到lowcost中,为0的不参与比较,所以lowcost=[0,0,0,0,0,0,0,0,0] ,adjvex={0,0,8,7,7,0,1,6,1},完成。

 

 

克鲁斯卡尔(Kruskal)算法

普里姆(Prim)算法是以某顶点为起点,逐步找各顶点上最小权值的边来构建最小生成树。直接以边为目标构建,权值在边上,直接找最小权值的边来构建生成树,在构建时要考虑是否会形成环路,因此用到图的存储结构中的边集数组结构。

/*对边集数组Edge的定义*/
typedef struct{
   int begin;
   int end;
   int weight;
}Edge;

将图转变为对应的边集数组,并且将它们按权值由小到大排序,如下图所示:
这里写图片描述

数组 begin end weight
edges[0] 4 7 7
edges[1] 2 8 8
edges[2] 0 1 10
edges[3] 0 5 11
edges[4] 1 8 12
edges[5] 3 7 16
edges[6] 1 6 16
edges[7] 5 6 17
edges[8] 1 2 18
edges[9] 6 7 19
edges[10] 3 4 20
edges[12] 3 8 21
edges[13] 3 6 24
edges[14] 4 5 26
/*Kruskal算法生成最小生成树,边集数组,时间复杂度O(eloge)*/
void MiniSpanTree_Kruskal(MGraph G){
   int i,n,m;
   Edge edges[MAXEDGE]; //定义边集数组,MAXEDGE边数极大值
   int parent[MAXVEX];  //判断边与边是否形成环路
   /*省略将邻接矩阵G转化为边集数组edges并按权由小到大排序的代码,形成edges一维数组*/
   for(i=0;i0) f=parent[f];
   return f;
}

开始i=0,查询边集数组得到(v4,v7),此时parent中都为0,所以n=4,m=7,parent[4]=7,parent数组值为{0,0,0,0,7,0,0,0,0},将 (v4,v7) 纳入到最小生成树。

然后i=1,查询边集数组,edges[1]得到边(v2,v8),n=2,m=8,parent[2]=8,parent数组值为{0,0,8,0,7,0,0,0,0},将 (v2,v8) 纳入到最小生成树。

然后i=2,查询边集数组,edges[2]得到边(v0,v1),n=0,m=1,parent[0]=1,parent数组值为{1,0,8,0,7,0,0,0,0},将 (v0,v1) 纳入到最小生成树。

然后i=3,查询边集数组,edges[3]得到边(v0,v5),由于parent[0]=1,所以n=1,m=5,parent数组值为{1,5,8,0,7,0,0,0,0},将 (v0,v5) 纳入到最小生成树。

然后i=4,查询边集数组,edges[4]得到边(v1,v8),由于parent[1]=5,parent[5]=0,所以n=5,m=8,parent数组值为{1,5,8,0,7,8,0,0,0},将 (v1,v8) 纳入到最小生成树。

然后i=5,查询边集数组,edges[5]得到边(v3,v7),由于parent[3]=0,parent[7]=0,所以n=3,m=7,parent数组值为{1,5,8,7,7,8,0,0,0},将 (v3,v7) 纳入到最小生成树。

然后i=6,查询边集数组,edges[6]得到边(v1,v6),由于parent[1]=5,parent[5]=8,parent[8]=0所以n=8,m=6,parent数组值为{1,5,8,7,7,8,0,0,6},将 (v1,v6) 纳入到最小生成树。

然后i=7,查询边集数组,edges[7]得到边(v5,v6),由于parent[5]=8,parent[8]=6,parent[6]=0所以n=6,m=6,m=n,所以退出循环,不添加该边。

然后i=8,查询边集数组,edges[8]得到边(v1,v2),由于parent[1]=5,parent[5]=8,parent[8]=6,parent[6]=0,parent[2]=8所以n=6,m=6,m=n,所以退出循环,不添加该边。

然后i=9,查询边集数组,edges[9]得到边(v6,v7),由于parent[6]=0,parent[7]=0,所以n=6,m=7,parent数组值为{1,5,8,7,7,8,7,0,6},将 (v6,v7) 纳入到最小生成树。

此后面的循环均会造成环路,最终最小生成树的构造过程如下:

这里写图片描述

小结:Kruskal算法针对边展开,边数少时效率很高,即对稀疏图有很大优势;Prim算法对于稠密图,即边数非常多时会更好。

相关TAG标签
上一篇:使用SpringSecurity3实现RBAC权限管理
下一篇:小算法--数组中元素的移动
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站