例题链接

以本题为例讲解

概述

求最小生成树的两种算法：
1.Kruskal算法
2.Prim算法

熟悉实现思路

下面的讲解比较好，代码可以看我写的。
这写的也太好了吧（我真的不是懒）

Kruskal算法（比较简单）

本质是 贪心+并查集
这个方法我记得离散数学学过，老师称其“避圈法”。
田呈亮yyds！！！

//最小生成树板子 Kruskal算法 并查集实现 
#include<bits/stdc++.h>
#define ll long long

using namespace std;
const int N=5100;
int a,b,fa[N],rx,ry,n,m;
ll c,ans;

struct edge
{
    int u,v;
    ll w;     
}e[N<<1];
bool cmp(edge a,edge b)
{
    return a.w<b.w;
}
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        e[i].u=a;
        e[i].v=b;
        e[i].w=c;
    }
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        rx=find(e[i].u);
        ry=find(e[i].v);
        if(rx!=ry)
        {
            ans+=e[i].w;
            fa[rx]=ry;
        }
    }
    cout<<ans<<endl;
}

Prim算法

链式前向星实现（未优化）

因为我所看的大佬的题解是通过“链式前向星”写的，又因为没学过，所以恶补了一下，发现不难。
链式前向星讲解 

//最小生成树板子 Prim算法 链式前向星实现 
/*
说在前面，注意：
注意区别数组的下标，
比如e数组的下标的含义为边的编号，而dis数组的下标的含义为点的编号，
所以在循环的时候要注意区分i的含义。
同时dis[i]表示编号为i的点到已选点集的最小距离（边权）
*/
#include<bits/stdc++.h>
#define ll long long
const int N=5005;
const int M=2e5+10;
const int INF=0x3f3f3f3f;
using namespace std;

struct edge
{
    int v,w,next;
}e[M<<1];//无向图开两倍

int n,m,cnt;
int vis[N],dis[N],head[N];

void add(int u,int v,int w)//链式向前星 加边操作 
{
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;    
}

int prim()
{
    ll ans=0;
    int minn=INF,now=1,tot=0;

    for(int i=1;i<=n;i++) dis[i]=INF;//将距离都初始化为极大值 
    for(int i=head[1];i;i=e[i].next) dis[e[i].v]=min(dis[e[i].v],e[i].w);

    while(++tot<n)
    {
        vis[now]=1;minn=INF;//每次循环都要初始化 

        //注意这里不是枚举now点的所有连边，而是1~n
        for(int i=1;i<=n;i++)//注意这里遍历的是点的编号 
        if(!vis[i]&&dis[i]<minn)
        minn=dis[i],now=i;//找到最小的边，就是要加的边 

        for(int i=head[now];i;i=e[i].next)//注意这里遍历的是边的编号 
        {
            int v=e[i].v;//边对应的点 
            if(!vis[v]&&e[i].w<dis[v]) dis[v]=e[i].w;//更新dis 
        }

        ans+=minn;//加边 
    }

    return ans;
}


int main()
{
    cin>>n>>m;
    for(int i=1,u,v,w;i<=m;i++)
    {
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    cout<<prim()<<endl;
}

链式前向星（优先队列优化）

/*
确实和Dijkstra优先队列优化很像，所以不多解释了，另附Dijkstra算法优先队列优化代码
*/
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=5005;
const int M=2e5+10;
const int INF=0x3f3f3f3f;

int head[N],cnt;
int n,m,vis[N],dis[N],ans,tot;

struct edge
{
    int v,w,next;    
}e[M<<1];

void add(int u,int v,int w)
{
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}

int prim()
{

    priority_queue<pii,vector<pii>,greater<pii> > q;
    q.push(pii(0,1));
    fill(dis+1,dis+n+1,INF);

    while(!q.empty() && tot<n)
    {
        int d=q.top().first,u=q.top().second;
        q.pop();//勿忘 
        if(vis[u]) continue;

        ++tot;
        vis[u]=1;//勿忘 
        ans+=d;

        for(int i=head[u];i;i=e[i].next) 
        {
            int v=e[i].v;
            if(dis[v]>e[i].w)
            dis[v]=e[i].w,q.push(pii(e[i].w,v));
        }
    }
    return ans;
}
int main()
{
    cin>>n>>m;
    for(int i=1,u,v,w;i<=m;i++)
    {
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    cout<<prim()<<endl;
    return 0;
}

另附

Dijkstra优先队列优化