图论 MST(最小生成树) prim

ybjnb / 2024-10-17 / 原文

Prim算法实现最小生成树

复杂度 O(n^2)

Prim算法是一种用于寻找加权无向图中最小生成树的贪心算法。以下是使用C++实现Prim算法的代码，包括详细的注释说明。

代码注释

#include <bits/stdc++.h>  // 包含所有标准库头文件
using namespace std;      // 使用标准命名空间

const int P = 1e6 + 7;    // 定义一个大素数，用于模运算（虽然在这个算法中并未使用）
const int inf = 1e9;      // 定义无穷大常量，用于初始化边的权重
typedef long long ll;      // 定义长整型别名

int mp[1010][1010];       // 邻接矩阵，存储图的边的权重
int n, m;                 // 分别存储节点数和边数
int d[1010];              // 存储从已选点到i的最小权值
int vis[1010];            // 标记节点是否被选中

// Prim算法的实现
void prim() {
    for (int i = 1; i <= n; i++)
        d[i] = inf;       // 初始化d数组，所有值设为无穷大
    d[1] = 0;              // 从节点1开始，d[1]设为0
    int ans = 0;           // 初始化最小生成树的总权重

    for (int s = 1; s <= n; s++) {
        int mi = inf; int id = -1;  // 初始化最小值和对应的节点id
        for (int i = 1; i <= n; i++) {
            if (d[i] < mi && vis[i] == 0) {  // 找到未访问的最小d值
                mi = d[i];
                id = i;
            }
        }
        if (id == -1) {  // 如果没有找到未访问的节点，说明图不连通
            cout << -1; return;
        }
        ans += mi;       // 将最小权值加入总权重
        vis[id] = 1;     // 标记节点id为已访问

        // 更新d数组，找到通过已访问节点到未访问节点的最小权值
        for (int i = 1; i <= n; i++) {
            if (vis[i] == 0 && mp[id][i] < d[i])
                d[i] = mp[id][i];
        }
    }
    cout << ans;  // 输出最小生成树的总权重
    return;
}

int main() {
    ios::sync_with_stdio(0);  // 关闭cin和cout的同步
    cin.tie(0);               // 解除cin和cout的绑定
    cout.tie(0);              // 解除cout和cout的绑定

    cin >> n >> m;             // 读取节点数和边数

    // 初始化邻接矩阵，所有边的权重设为无穷大
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            mp[i][j] = inf;
        }
    }
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;  // 读取边的两个节点和权重
        if(mp[a][b] > c)     // 如果存在更小的权重，则更新
            mp[a][b] = mp[b][a] = c;
    }
    prim();  // 调用Prim算法函数
    return 0;
}