本文共 1681 字，大约阅读时间需要 5 分钟。

题目链接：

prim算法：算法从任意一个顶点开始，每次选择一个与当前顶点集最近的一个顶点，并将两顶点之间的边加入到树中。Prim算法在找当前最近顶点时使用到了贪婪算法。

代码实现：

#include
   
    using namespace std;const int maxn=105;const int INF=0x3f3f3f3f;//初始化无穷大int dis[maxn];//dis[i]//记录边权bool vis[maxn];//标记边int edge[maxn][maxn];void prim(int n){    for(int i=1;i<=n;i++) dis[i]=edge[1][i];//初始时候记录1到其他顶点距离    int ans=0;    dis[1]=0;    vis[1]=true;//将用过的点标记，避免重复访问    for(int i=2;i<=n;i++)//进行n-1次操作    {        int u=INF;        int pos;//记录最小权值的顶点的下标        for(int j=1;j<=n;j++)//在未加入点中，找到一个最小的权值        {            if(!vis[j]&&u>dis[j])            {                u=dis[j];//更新最小值                pos=j;            }        }        if(u==INF) break;//图不是连通图        vis[pos]=true;//将加入点进行标记        ans+=u;//加边权        for(int j=1;j<=n;j++)//枚举所有点        {//在未加入点中找到与此点相连的权值最小的边            if(!vis[j]&&dis[j]>edge[pos][j])            {                dis[j]=edge[pos][j];//更新权值            }        }    }    printf("%d\n",ans);}int main(){    int n;    while(scanf("%d",&n)&&n)    {        memset(vis,false,sizeof(vis));        int m=(n-1)*n/2;        for(int i=1;i<=m;i++)        {            int u,v,w;            scanf("%d%d%d",&u,&v,&w);            edge[u][v]=edge[v][u]=w;        }        prim(n);    }    return 0;}
   

kruskal算法：

kruskal算法主要是加边，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。

代码：

#include
   
    using namespace std;const int maxn=1e4+5;typedef long long LL;int father[maxn];struct node{    int u,v,val;//u-v之间边权为val}edge[maxn];bool cmp(node a,node b)//按照边权小到大排序{    return a.val
   

转载地址：https://dh-butterfly.blog.csdn.net/article/details/81414160 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！