prim算法是以一个根节点开始慢慢往下延伸，不断寻找距生成树最短的距离的节点，然后将该节点纳入生成树的集合中，然后再将该节点影响的其他未纳入生成树节点的距离更新。（缩小与生成树的距离），重复操作，直至全部节点纳入集合或者没有节点纳入集合为止。
prim算法的时间复杂度为O（V^2）；
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn=1005;
const int INF=0x3f3f3f3f;
int p[maxn]; //储存父节点
int edge[maxn][maxn];//邻接矩阵
int d[maxn]; //到生成树的最短距离
int vis[maxn];//是否加入集合中
int n,m;
//初始化
void init()
{
memset (vis,0,sizeof(vis));
memset (p,-1,sizeof(p));
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
i==j? edge[i][j]==0:edge[i][j]=INF;
}
void prim()
{
//以1作为根节点
for (int i=1;i<=n;i++)
{
if(edge[1][i]!=INF)
p[i]=1;
d[i]=edge[1][i];
}
while (1)
{
int maxx=INF;
int u=-1;
//找到距离生成树最短距离的节点
for (int i=1;i<=n;i++)
{
if(!vis[i]&&d[i]<maxx)
{
maxx=d[i];
u=i;
}
}
if(u==-1)
break;
//将选出的节点纳入集合
vis[u]=1;
//更新该节点影响的节点
for (int i=1;i<=n;i++)
{
if(!vis[i]&&d[i]>edge[u][i])
{
d[i]=edge[u][i];
p[i]=u;
}
}
}
int sum=0;
for (int i=1;i<=n;i++)
if(p[i]==-1)
{
printf("不存在最小生成树\n");
return ;
}
else
sum+=d[i];
printf("最短生成树的长度为%d\n",sum);
return ;
}
void parent ()
{
for (int i=1;i<=n;i++)
if(p[i]!=-1&&p[i]==i)
printf("%d为根节点\n",i);
else if(p[i]!=-1)
printf("%d的父节点为%d\n",i,p[i]);
}
int main()
{
scanf("%d%d",&n,&m);
init();
for (int i=1;i<=m;i++)
{
int x,y,sp;
scanf("%d%d%d",&x,&y,&sp);
edge[x][y]=edge[y][x]=sp;
}
prim();
parent();
return 0;
}
/*运行结果
6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3
最短生成树的长度为12
1为根节点
2的父节点为5
3的父节点为6
4的父节点为3
5的父节点为3
6的父节点为1*/
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
