定义：一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。

一个有N个点的图，边一定是大于等于N-1条的。图的最小生成树，就是在这些边中选择N-1条出来，连接所有的N个点。这N-1条边的边权之和是所有方案中最小的。

通俗的来讲：给定一个无向图，在图中选择若干条边把图的所有节点连起来。要求边长之和最小。在图论中，叫做求最小生成树。

如果要求一个图的最小生成树，可以用prim和kruskal算法

1.prim

类似于dijkstra算法

int dist[n],state[n],pre[n];
dist[1] = 0;
for(i : 1 ~ n)
{
    t <- 没有连通起来，但是距离连通部分最近的点;
    state[t] = 1;
    更新 dist 和 pre;
}

参考之前的代码，我们不难得到：（带注释）

#include <iostream>
#include <cstring>
const int N=510,INF=0x3f3f3f3f;
int g[N][N];
int n,m;
int dis[N];
bool st[N];

using namespace std;
int prim(){
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    int  res=0;
    for(int i=1;i<=n;i++){
        int t=-1;
        for(int j=1;j<=n;j++) {
            if (!st[j]&&(t == -1 || dis[t] > dis[j])){
//j不在集合中，找到最小dis
                t=j;
            }
        }
        if(i!=1&&dis[t]==INF) return INF;
//i不是第一个点，如果最短的dis为INF，说明不联通，没有最短路，直接返回
        res+=dis[t];//累积求和
        st[t]=1;

        for(int j=1;j<=n;j++){
            dis[j]=min(dis[j],g[t][j]);
//与dijkstra不同，这里不需要dis[t]+g[t][j]应为我们是累加，而不是求每一个点到第一点的最短距离。    
 }
    }
    return res;
}

int main(){
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    while(m--){

        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=g[b][a]=min(g[a][b],c);//注意是无向边
    }
    int t=prim();
    if(t==INF) puts("impossible");
    else cout<<t;
    return 0;
}

有了之前的经验，我们直到，这里也可以用堆优化：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;

typedef long long LL;
typedef pair<LL ,LL >PII;
const int N=1e6;

LL n,m,resmax;
LL e[N],ne[N],w[N],idx=0,h[N];
LL res[N];
bool st[N];

void add(int a,int b,LL ww)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=ww,h[a]=idx++;
}

void bfs()
{
    priority_queue<PII,vector<PII>,greater<PII>> q;
    memset(res,0x3f,sizeof res);
    res[1]=0;
    q.push({0,1});
    while(q.size())
    {
        auto t=q.top();
        q.pop();
        if(st[t.second]) continue;
        st[t.second]=true;

        for(int i=h[t.second];i!=-1;i=ne[i])
        {
            int k=e[i];
            if(res[k]>w[i]&&!st[k])
            {
                res[k]=w[i];//这一块不太一样
                q.push({res[k],k});
            }
        }
    }
}
int main()
{
   
    cin>>n>>m;
    memset(h,-1,sizeof h);

    for(int i=0;i<m;i++)
    {
        LL a,b,ww;
        cin>>a>>b>>ww;
        add(a,b,ww);
        add(b,a,ww);
    }
    bfs();

    for(int i=2;i<=n;i++)
    {
        resmax=resmax+res[i];
        if(res[i]>0x3f3f3f3f)
        {
            cout<<"impossible";
            return 0;
        }
    }

    cout<<resmax;
}

2.kruskal

思路非常简单，算法实现类似于之前的并查集。

算法思路：

将所有边按照权值的大小进行升序排序，然后从小到大一一判断。

如果这个边与之前选择的所有边不会组成回路，就选择这条边分；反之，舍去。

直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。

筛选出来的边和所有的顶点构成此连通网的最小生成树。

判断是否会产生回路的方法为：使用并查集。

在初始状态下给各个个顶点在不同的集合中。

遍历过程的每条边，判断这两个顶点的是否在一个集合中。

如果边上的这两个顶点在一个集合中，说明两个顶点已经连通，这条边不要。如果不在一个集合中，则要这条边。

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010, INF = 0x3f3f3f3f;

int n, m;
int p[N];
struct Edge{
    int a,b,w;
    //重载运算符
    bool operator< (const Edge&W)const{
        return w<W.w;
    }
}edges[M];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal(){
    sort(edges,edges+m);
    for(int i=1;i<=n;i++) p[i]=i;
    int cnt=0,res=0;
    for(int i=0;i<m;i++){
        int a=edges[i].a,b=edges[i].b,w=edges[i].w;
        int ra=find(a),rb=find(b);
        if(ra!=rb){
            p[ra]=rb;
            res+=w;
            cnt++;
        }
       
    } 
    if(cnt<n-1) return INF;
    return res;
}
int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 0; i < m; i ++ )
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edges[i] = {a, b, w};
    }

    int t = kruskal();

    if (t == INF) puts("impossible");
    else printf("%d\n", t);

    return 0;
}

如果重载运算符不理解可以换成：

bool cmp(struct Edge A, struct Edge B)
{
return A.w < B.w;
}
然后sort里加个参数 ： sort(edges, edges + m,cmp);