最小生成树

_shining · 2024-08-05 16:40:58 · 算法·理论

前言

最小生成树又称 MST，为边权和最小的生成树。

Kruskal

#include <bits/stdc++.h>//万能头文件
using namespace std;//命名空间
int fa[1000001];
int n, m, res, cnt;
struct poi{
    int x, y, z;
}g[1000001];
bool cmp(poi a, poi b)
{
    return a.z < b.z;
}
int find(int x)//并查集 
{
    if(x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}
int main()//主函数
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++) cin >> g[i].x >> g[i].y >> g[i].z;
    stable_sort(g + 1, g + m + 1, cmp);//排序
    for(int i = 1; i <= n; i++) fa[i] = i;//并查集初始化 
    for(int i = 1; i <= m; i++){
        int x = find(g[i].x);//并查集 
        int y = find(g[i].y);//并查集 
        if(x == y) continue;//若出现两个点已经联通了，那么这一条边就不需要了
        fa[x] = y;//将y、x合并 
        res += g[i].z;//将边权计入答案
        cnt++;//边数++ 
    }
    if(cnt == n - 1) cout << res;
    else cout << "No MST";//没有最小生成树 
    return 0;//华丽结束
}

Prim

O(n^2)

#include <bits/stdc++.h>//万能头文件
using namespace std;//命名空间
bool vis[1001];
int n, m, res;
int a[1001][1001], d[1001];
void prim()
{
    memset(d, 0x3f, sizeof(d));
    memset(vis, 0, sizeof(vis));
    d[1] = 0;
    for(int i = 1; i <= n; i++){
        int x = 0;
        for(int j = 1; j <= n; j++){
            if(!vis[j] && d[j] < d[x]) x = j;
        }
        vis[x] = 1;
        for(int j = 1; j <= n; j++){
            if(!vis[j]) d[j] = min(d[j], a[x][j]);
        }
    }
}
int main()//主函数
{
    memset(a, 0x3f, sizeof(a));
    cin >> n >> m;
    for(int i = 1; i <= n; i++) a[i][i] = 0;
    for(int i = 1; i <= m; i++){
        int x, y, z;
        cin >> x >> y >> z;
        a[x][y] = a[y][x] = min(a[x][y], z);
    }
    prim();
    for(int i = 2; i <= n; i++) res += d[i];
    cout << res;
    return 0;//华丽结束
}