最小生成树（Kruskal+Prim）
最小生成树：
概念：在无向图中，连通且不含圈的图称为树。给定无向图 G =（V，E），连接 G 中所有点，且边集是 E 的子集的树称为 G 的生成树，而权值最小的生成树称为最小生成树（MST）。下面就介绍两个算法：Kruskal算法和Prim算法。
Kruskal算法
算法描述：克鲁斯卡尔算法需要对图的边进行访问，所以克鲁斯卡尔算法的时间复杂度只和边又关系。
算法过程：
1.将图各边按照权值进行排序
2.将图遍历一次，找出权值最小的边，（条件：此次找出的边不能和已加入最小生成树集合的边构成环），若符合条件，则加入最小生成树的集合中。不符合条件则继续遍历图，寻找下一个最小权值的边。
3.递归重复步骤1，直到找出n-1条边为止（设图有n个结点，则最小生成树的边数应为n-1条），算法结束。得到的就是此图的最小生成树。
克鲁斯卡尔（Kruskal）算法因为只与边相关，则适合求稀疏图的最小生成树。
如图：
代码（HDU 1233题 还是畅通工程）：
-
#include<stdio.h>
-
#include<algorithm>
-
using namespace std;
-
int n,m,ans;
-
int father[105];//记录父亲节点，开始都指向自己
-
struct zhang
-
{
-
int x,y,w;
-
-
}t[5009];
-
bool cmp(const zhang &a,const zhang &b)
-
{
-
return a.w < b.w ;//按权值从小到大排序
-
}
-
void kruskal()
-
{
-
int find(int x);
-
int x,y,i;
-
for(i=0;i<m;i++)
-
{
-
x=find(t[i].x);
-
y=find(t[i].y);
-
if(x!=y)
-
{
-
father[x]=y;
-
ans+=t[i].w;
-
}
-
}
-
}
-
int find(int x)//查找父亲节点
-
{
-
if(father[x]!=x)
-
x=find(father[x]);
-
return x;
-
}
-
int main()
-
{
-
int i;
-
while(scanf("%d",&n)!=EOF)
-
{
-
ans=0;
-
if(n==0)
-
break;
-
m=n*(n-1)/2;
-
for(i=1;i<=n;i++)
-
father[i]=i;
-
for(i=0;i<m;i++)
-
scanf("%d%d%d",&t[i].x,&t[i].y,&t[i].w);
-
sort(t,t+m,cmp);
-
kruskal();
-
printf("%d\n",ans);
-
}
-
return 0;
-
}
-
Prim算法
普里姆算法的基本思想：
从图G={V,E}中的某一顶点U0出发，选择与它关联的具有最小权值的边(U0,v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合U中。如此继续下去，直到图中的所有顶点都加入到生成树顶点集合U中为止。
算法描述：Prim算法需要对图的顶点进行访问，所以Prim算法的时间复杂度只和图中的顶点有关系，所以适合求稠密图的最小生成树。
任意指定一个顶点作为起始点，放在S中(一般选1点)。
每一步将最短的特殊边放入S中，需要n-1步，即可把所有的其他的点放入S中。算法结束。
如图：
代码（NOJ 502题 筹建工程）：
-
#include<stdio.h>
-
#include<string.h>
-
#define INF 9999999
-
int ans,m,q;
-
int vis[102],low[102],map[102][102];
-
void prim()
-
{
-
int i,j,k;
-
for(i=2;i<=m;i++)
-
low[i]=map[1][i];
-
vis[1]=1;
-
q=1;
-
for(i=2;i<=m;i++)
-
{
-
int x=1,min=INF;
-
for(j=2;j<=m;j++)//寻找最小边
-
if(!vis[j]&&low[j]<min)
-
{
-
x=j;
-
min=low[j];
-
}
-
ans+=min;
-
if(x==1)
-
break;
-
q++;
-
vis[x]=1;//标记顶点
-
for(k=2;k<=m;k++)
-
if(!vis[k]&&low[k]>map[x][k])
-
low[k]=map[x][k];
-
}
-
}
-
int main()
-
{
-
int T,i,j,n,x,y,z;
-
scanf("%d",&T);
-
while(T--)
-
{
-
memset(vis,0,sizeof(vis));
-
scanf("%d%d",&n,&m);
-
for(i=1;i<=m;i++)
-
for(j=1;j<=m;j++)
-
if(i!=j)
-
map[i][j]=INF;
-
else
-
map[i][j]=0;
-
for(i=0;i<n;i++)
-
{
-
scanf("%d%d%d",&x,&y,&z);
-
map[x][y]= map[y][x]=z;
-
}
-
ans=0;
-
prim();
-
if(q==m)
-
printf("%d\n",ans);
-
else
-
printf("No solution\n");
-
}
-
return 0;
-
}
文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nyist_zxp/article/details/9615003
- 点赞
- 收藏
- 关注作者
评论（0）