最小生成树

ERA_YES / 2023-05-18 / 原文

最小生成树

最小生成树（Minimum Spanning Tree，简称 MST）是连接所有节点的边的集合中，权值最小的连通子图的边集合，即一个加权连通图中，找到一棵生成树，使得所有边的权值之和最小。最小生成树的求解算法主要有两种：

Kruskal 算法

Kruskal 算法也是一种贪心算法，将所有边按照权值`从小到大排序，逐个加入到已有的边集合中，直到所有节点都被覆盖。具体步骤如下：

将所有边按照权值从小到大排序。

依次将每条边加入到已有的边集合中，如果加入该边后形成了环，则舍弃该边。

重复步骤（2），直到所有节点都被覆盖。

需要注意的是，无向图的最小生成树可能不唯一，但最小生成树的边数是固定的，即节点数减一。

时间复杂度分析

O(ElogE)或者O(ElogV)，其中E代表图中的边的数目，V代表图中的顶点数目。对图中的边按照非降序排列需要O(ElogE)的时间。排序后遍历所有的边并判断添加边是否构成环，判断添加一条边是否构成环最坏情况下需要O(logV)，关于这个复杂度等到景禹给你们谈并查集的时候再分析；因此，总的时间复杂度为O(ElogE + ElogV)，其中E的值最大为V(V-1)/2，因此O(logV)等于 O(logE)。因此，总的时间复杂度为O(ElogE) 或者O(ElogV)。

代码

C++

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;
int fa[maxn];

struct Edge{
    int u, v, w;
    bool operator<(const Edge &other) const{ //重载操作符
        return w < other.w;
    }
}e[maxn];

int find(int x){
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

int main(){
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; i++){
        cin >> e[i].u >> e[i].v >> e[i].w;
    }

    sort(e + 1, e + m + 1);

    for (int i = 1; i <= n; i++){
        fa[i] = i;
    }

    int ans = 0, cnt = 0;
    for (int i = 1; i <= m; i++){
        int fu = find(e[i].u), fv = find(e[i].v);
        if (fu != fv){
            fa[fu] = fv;
            ans += e[i].w;
            cnt++;
        }
        if (cnt == n - 1){
            break;
        }
    }

    cout << ans << endl;

    // 测试代码
    /*
    for (int i = 1; i <= n; i++) {
        cout << find(i) << " ";
    }
    cout << endl;
    */

    return 0;
}

Prim 算法

Prim 算法是一种贪心算法，它的基本思想是先将图中的所有边按照权值从小到大排序，然后依次选择边，如果该边的两个端点不在同一个集合中，则将该边加入生成树中。最终生成的树即为最小生成树。从任意一个节点开始，每次选择权值最小的一条边，加入到已有的边集合中，直到所有节点都被覆盖。具体步骤如下：

从任意一个节点开始，将其加入到已有的节点集合中。

选择与已有节点集合距离最小的一条边，将其加入到已有的边集合中。

将该边的另一个节点加入到已有的节点集合中。

重复步骤（2）和（3），直到所有节点都被覆盖。

不同于Kruskal算法，Prim算法每次只考虑一个节点和生成树之间的边，因此在稠密图中效率更高。

时间复杂度分析

上面的代码中，当 i == 1的时候，内层的 while 与 for 循环中 j 的取值范围是从 1 到 n-1，内循环一共计算了 2(n-1) 次，其中n为图中的顶点个数；当 i == 2 的时候，内层循环还是一共计算 2(n-1)次；以此类推...... i 取最大值 n -1，内层循环还是一共计算2(n-1)次；所以，整体的执行次数就是(n-1) \* 2(n-1)，Prim算法的复杂度是 O(n2)级别的。

代码

C++

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;

int n, m;
int dis[maxn], vis[maxn];
int g[maxn][maxn];

int prim() {
    memset(dis, INF, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[1] = 0;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int u = 0;
        for (int v = 1; v <= n; v++) {
            if (!vis[v] && (u == 0 || dis[v] < dis[u])) {
                u = v;
            }
        }
        vis[u] = 1;
        ans += dis[u];
        for (int v = 1; v <= n; v++) {
            if (!vis[v] && g[u][v] < dis[v]) {
                dis[v] = g[u][v];
            }
        }
    }
    return ans;
}

int main() {
    cin >> n >> m;
    memset(g, INF, sizeof(g));
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = w;
    }
    int ans = prim();
    cout << ans << endl;
    return 0;
}