C++

$\color{#cc33ff}{— > 算法基础课题解}$

朴素prim 算法:

1、首先初始化所有点的距离为 INF
2、迭代 n 次

• 找到集合外距离最近的点，以 t 表示
• 用 t 来更新其他点到集合的距离
• 把 t 加入到集合中（st[t] = true）

$图解：$

#include<iostream>
#include<cstring>
#include<algorithm>

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]); // 以t更新其他点到集合的距离

        st[t] = true; // 入树
    }

    return res;
}

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

    memset(g, 0x3f, sizeof g); // 把所有点之间的距离初始化为正无穷

    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 == INF) cout << "impossible"; // 不存在生成树（所有点不连通）
    else cout << t;

    return 0;
}