51 nod Prim算法&Kruskal算法（贪心之最小生成树、Prim、Kruskal）

第1行：2个数N,M中间用空格分隔，N为点的数量，M为边的数量。（2 <= N <= 1000, 1 <= M <= 50000)
第2 - M + 1行：每行3个数S E W，分别表示M条边的2个顶点及权值。(1 <= S, E <= N，1 <= W <= 10000)

输出最小生成树的所有边的权值之和。

9 14
1 2 4
2 3 8
3 4 7
4 5 9
5 6 10
6 7 2
7 8 1
8 9 7
2 8 11
3 9 2
7 9 6
3 6 4
4 6 14
1 8 8

37

（1）Prim算法模板：

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int Map[1005][1005];
int main()
{
int n,m,a,b,c;
cin>>n>>m;
int vis[n+1];
memset(vis,0,sizeof(vis));
memset(Map,INF,sizeof(Map));
for(int i=1;i<=m;i++)
{
cin>>a>>b>>c;
if(c<Map[a][b])
Map[a][b]=Map[b][a]=c;
}
vis[1]=1;
int dis[n+1];
for(int i=1;i<=n;i++)
dis[i]=Map[1][i];///将初始点看做一棵树，并将附近与树相邻的点的边都记录下来
int Min,index,sum=0;
for(int i=2;i<=n;i++)
{
Min=INF;
for(int j=1;j<=n;j++)
{
if(!vis[j]&&dis[j]<Min)///将当前整棵树相邻的最小边加入树中
{
Min=dis[j];
index=j;
}
}
vis[index]=1;///点被标记，防止点重复加入树中
sum+=Min;///权值增加
for(int j=1;j<=n;j++)
{
if(!vis[j]&&dis[j]>Map[index][j])///更新当前整棵树与未连接的点的最小边
dis[j]=Map[index][j];
}
}
printf("%dn",sum);
return 0;
}

Prim算法中有双重for循环，时间复杂度为O（n^2），其中n为图的顶点个数。Prim算法执行的时间与图中的边数无关，与点的个数有关，所以Prim算法适合于稠密图求最小生成树。

（2）Kruskal算法模板：

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define Max 1005
using namespace std;
int Map[Max][Max];
int father[Max];
int n,m;
struct node
{
int a,b,c;
}p[50005];
int cmp(node p1,node p2)///边的排序按照权值从小到大排列
{
return p1.c<p2.c;
}
int Find(int i)///判断是或否连通
{
return i==father[i]?i:father[i]=Find(father[i]);
}
void Merge(int a,int b)///连接两个点
{
int fa=Find(a);
int fb=Find(b);
if(fa!=fb)
father[fb]=fa;
}
void Kruskal()
{
int k=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
if(Map[i][j]!=INF&&Map[i][j]!=0)///将边进行整理
{
p[k].a=i;
p[k].b=j;
p[k].c=Map[i][j];
k++;
}
sort(p,p+k,cmp);///将边按照升序排序
for(int i=1;i<=n;i++)
father[i]=i;
int j=1;
k=0;
int sum=0;///记录整棵树的权值
while(j<m&&k<n)///k<n是因为N个点，连通各点一次仅需要n-1条边
{
int fa=Find(p[j].a);
int fb=Find(p[j].b);
if(fa!=fb)
{
sum+=p[j].c;
k++;
Merge(p[j].a,p[j].b);
}
j++;
}
cout<<sum<<endl;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
Map[i][i]=0;
for(int j=1;j<i;j++)
{
Map[i][j]=Map[j][i]=INF;
}
}///初始化矩阵
int a,b,c;
for(int i=1;i<=m;i++)
{
scanf("%d %d %d",&a,&b,&c);
if(Map[a][b]>c)
Map[a][b]=Map[b][a]=c;
}
Kruskal();
return 0;
}

最后

以上就是迷路鸡翅为你收集整理的51 nod Prim算法&Kruskal算法（贪心之最小生成树、Prim、Kruskal）的全部内容，希望文章能够帮你解决51 nod Prim算法&Kruskal算法（贪心之最小生成树、Prim、Kruskal）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。