Prim

Prim算法求最小生成树
与dijkstra算法类似，dijkstra算法是计算一个节点到其他节点的最短路，Prim算法是需要维护节点到一个集合的距离最小值，优化方式也是类似的，只需要用堆来维护距离即可

#include <bits/stdc++.h>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N]; //邻接矩阵存图
int dist[N]; //距离数组
bool st[N];  //判断当前点是否被用到
int prim()
{
    memset(dist, 0x3f, sizeof(dist));
    int res = 0;
    for (int i = 0; i < n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++) //找到未在集合中的点距离当前集合最近的点
        {
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        if (i && dist[t] == INF) //表示第一次用到的这个点与集合不连通，即没有最小生成树
            return INF;
        if (i) //如果不是第一次的话，将距离叠加，只有一个点没有最小生成树的概念
            res += dist[t];
        for (int j = 1; j <= n; j++) //用这个点的距离更新这个点到集合的距离
            dist[j] = min(dist[j], g[t][j]);
        st[t] = true;
    }
    return res;
}
int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof(g));
    while (m--)
    {
        int a, b, w;
        cin >> a >> b >> w;
        g[b][a] = g[a][b] = min(g[a][b], w);
    }
    int t = prim();
    if (t == INF) //当所有点不连通的时候，不存在最小生成树
        cout << "impossible" << endl;
    else
        cout << t << endl;
    return 0;
}

Kruskal

Kruskal算法求最小生成树
将图中的边按权重排序，遍历每一条边，如果两条边不连通，就连在一起
这里使用了并查集维护每一条边

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, m;
int p[N]; //用并查集，维护边的权重，降低时间复杂度
struct Edge
{
    int a, b, w;
    bool operator<(const Edge &W) const
    {
        return w < W.w;
    }
} edges[N];
int find(int x) //并查集中找祖宗节点+优化的函数
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }
    sort(edges, edges + m);
    for (int i = 1; i <= n; i++) //初始化并查集
        p[i] = i;
    int res = 0; //存储最小生成树中所有边的权重之和
    int cnt = 0; //存储当前一共加了多少条边
    for (int i = 0; i < m; i++)
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        a = find(a), b = find(b); //并查集中的算法
        if (a != b)
        {
            p[a] = b;
            res += w;
            cnt++;
        }
    }
    if (cnt < n - 1) //表示存在不连通的点，即不存在最小生成树
        cout << "impossible" << endl;
    else //输出答案
        cout << res << endl;
    return 0;
}