小编点评

**算法流程：** 1. 初始化所有距离为正无穷，保存已经选的点集合。 2. 遍历所有点，找到距离最小的点并加入集合。 3. 对于每个点，更新其距离所有点距离的最小值。 4. 如果当前点距离所有点距离已达到最大值，则无法加入集合，返回不符合条件。 5. 遍历所有连接当前点的边，如果这条边与当前选出的边不在同一个集合中，则加入集合并更新其距离。 6. 返回最小生成树的边数。 **Kruskal算法的流程：** 1. 将所有边按照权值从小到大排序。 2. 遍历所有边，如果这条边与当前选出的所有边不在同一个集合中，则加入集合并更新其距离。 3. 选择具有最小距离的边，直到选出了N-1条边。 4. 如果当前边数不等于N-1，则无法构造最小生成树，返回不符合条件。 5. 返回最小生成树的边数。 **时间复杂度：** * 最小生成树算法：O(n * log(m)) * Kruskal算法：O(n * log(m))

正文

什么是最小生成树

给定一个图，在图中选择N - 1条边（N代表图的点数）把图的所有节点都连起来，且边的权值最小，则这N - 1条边就是原图的最小生成树。

如何求最小生成树

求最小生成树有两种算法：

1. prim

2. kruskal

prim算法

其实本质上和dijstra算法很像。

适用于稠密图。

题目：

算法流程：

1. 将所有点到已经选的点的集合的距离设为正无穷。

2. 每次找到dis最小的点，加入到集合中。

3. 使用该点的距离更新所有点到集合距离（注意：我们之前已经确定过的点不需要再被改变dis，所以说我们要特殊确定一下）。

代码：

#include <bits/stdc++.h>
#define N 510
using namespace std;
int n, m;
int g[N][N];
int dis[N];
bool st[N];
int prim() {
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        int minid = -1; //	dis最小的点
        for (int j = 1; j <= n; ++j)
            if (!st[j] && (minid == -1 || dis[j] < dis[minid]))
                minid = j;
        if (dis[minid] == 0x3f3f3f3f)
            return 0x3f3f3f3f; //	不符合条件
        ans += dis[minid];
        st[minid] = true;
        for (int j = 1; j <= n; ++j)
            dis[j] = min(dis[j], g[minid][j]); //	更新距离
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    memset(g, 0x3f, sizeof g);
    cin >> n >> m;
    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 == 0x3f3f3f3f)
        puts("impossible");
    else
        cout << t << '\n';
    return 0;
}

kruskal算法

适用于稀疏图。

题目：

前置知识：并查集

如果不会并查集，可以看我的另外一篇博客：【数据结构】并查集

算法流程：

1. 将所有边按照权值从小到大排序。
2. 如果这条边与之前选出来的所有边不会形成环（使用并查集判断），那么就使用这条边，否则舍去这条边。
3. 直到选出了N-1条边，算法结束。

代码：

#include <bits/stdc++.h>
#define N 100010
using namespace std;
int p[N]; //  并查集
struct Egde {
    int a, b, c;
    bool operator<(const Egde& t) const {
        return c < t.c;
    } //  按边权从小到大排序
} edges[N * 2];
int n, m;
int cnt, ans;
int find(int x) {
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}
void kruskal() {
    for (int i = 1; i <= m; ++i) {
        int a = find(edges[i].a), b = find(edges[i].b), c = edges[i].c;
        if (a != b) {
            ans += c;
            cnt++;
            p[a] = b;
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        p[i] = i;
    for (int i = 1; i <= m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c};
    }
    sort(edges + 1, edges + m + 1);
    kruskal();
    if (cnt < n - 1) { //  选出的边数不是N-1条，不符合条件
        puts("impossible");
        return 0;
    }
    cout << ans << '\n';
    return 0;
}