最小生成树：prim用于处理稠密图，因为他是以点为起点开始扩散，kruskal用于处理稀疏图，因为他以边为基准

Prim算法解决最小生成树问题，思路和Dijkstra很像
联系：Dijkstra算法是更新到起始点的距离，Prim是更新到生成树集合的距离

#include <iostream>
#include <cstring>

using namespace std;
const int N = 510, INF = 0x3f3f3f3f;

int g[N][N], dis[N]; //dis最小树集合到这个点的最短距离，而Dijkstra中表示到起点的最短距离
bool st[N]; // 是否在最小生成树集合中
int n, m;

int prim(){
    int res = 0;
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    
    for(int i = 0; i < n; ++i){
        int t = 0;
        for(int j = 1; j <= n; ++j){
            if(!st[j] && (t == -1 || dis[t] > dis[j]))
                t = j;
        }
        // 特判，如果到不来t号点
        if(i && dis[t] == INF) return INF;
        if(i) res += dis[t]; 
        st[t] = true;
        
        for(int j = 1; j <= n; ++j){
            dis[j] = min(dis[j], g[t][j]);  // 因为t已经在集合中且是集合中离集合外点最近的点，所以有t来更新其他点
        }
    }
    return res;
}

int main(){
    memset(g, 0x3f, sizeof g);
    scanf("%d%d", &n, &m);
    while(m --){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
        
    }
    int ans = prim();
    if(ans == 0x3f3f3f3f) puts("impossible");
    else printf("%d", ans);
    return 0;
}

Kruskal算法
思路：用结构体数组来存储每一条边，将边以权重来排序，从小到大选取如果会形成环则不选取

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 300000;

struct Edge{
    int a, b, v;
    bool operator < (const Edge& other) const{
        return v < other.v;
    }
}edges[N];

int n, m, p[100100];

// 并查集代码
int find(int x){
    if(x == p[x]) return p[x];
    else p[x] = find(p[x]);
}

int kruskal(){
    sort(edges, edges + m);
    for(int i = 1; i <= n; ++i) p[i] = i;
    int res = 0, cnt = 0;
    for(int i = 0; i < m; ++i){
        int a = edges[i].a, b = edges[i].b, v = edges[i].v;
        
        a = find(a), b = find(b);
        if(a != b){  // 如果这两个点不在一个集合中把两个点合并，并且加入这条边，如果在一个集合中会形成环
            p[a] = b;
            res += v;
            cnt ++;
        }
    }
    if(cnt < n - 1) return 0x3f3f3f3f; 
    return res;
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; ++i){
        int a, b, v;
        scanf("%d%d%d", &a, &b, &v);
        edges[i] = {a, b, v};
    }
    int ans = kruskal();
    if(ans == 0x3f3f3f3f) puts("impossible");
    else printf("%d\n", ans);
    return 0;
}