C++最小生成树 Prim 算法

Prim 算法：像滚雪球一样建最小生成树

这是什么，用来干什么？

生活中经常遇到这样的问题：几个村庄之间要修路，希望所有村庄都能连通，同时修路的总成本最小。这就是 最小生成树（Minimum Spanning Tree, MST） 问题。最小生成树是一张图里连接所有顶点（村庄）且总边权（成本）最小的树形结构。

Prim 算法是解决最小生成树问题的一种经典算法。它的思路非常自然：从任意一个顶点开始，每次挑选当前离“已选中的树”最近的一个顶点加入进来。 就像滚雪球一样，一开始只有一个小雪球，然后不断把附近的雪粘上来，越滚越大，最后变成一个覆盖所有顶点的大树。因为这个过程每次只选最近的点，所以也叫“贪心算法”。

生活中的例子：抓人游戏

想象你和几个朋友在操场上玩“抓人”游戏。一开始，你站在一个点上（起点）。然后你伸手抓住离你最近的一个朋友。现在你们两个人站在一起，成为一个“小队”。接着，你们一起伸手，抓住离小队最近的下一个人……这样一直抓，直到所有朋友都被抓到。这个过程中，每次抓的都是离“当前小队”最近的人，最后所有人聚在一起，而且抓人走过的总距离是最小的。

这个例子和 Prim 算法完全一致：每个朋友就是一个顶点，“离小队最近”就是距离当前最小生成树最近的顶点，抓人的路径就是一条边。

算法步骤详解

任意选一个起点（村庄0），标记为“已访问”。
初始化距离数组：用一个数组 dist 记录每个未访问村庄到当前树的最短距离。开始时，起点自己到自己的距离是0，其他村庄距离设为无限大。
循环 n 次（n 是村庄总数）：
- 在所有未访问的村庄中，找到 dist 值最小的那个村庄 u，把它加入树（标记为已访问），并将它的距离值加入总成本。
- 检查村庄 u 的所有邻居 v，如果 v 未访问，并且从 u 到 v 的边权比 dist[v] 更小，就更新 dist[v] 为这个更小的值。
重复步骤3，直到所有村庄都被访问。

关键：每次新增的顶点都是当前距离树最近的那个，这样保证总成本最小。这就是贪心的体现。

新手容易犯的错误

忘记初始化 dist[起点] = 0：如果起点距离不是0，算法会从无限大开始找最小值，导致错误。
图不连通：当图不是连通图时，算法会在某一步找不到可加入的顶点（u 仍为 -1），这时应该停止并处理。通常可以返回 -1 或提示错误。
用 = 而不是 < 更新距离：如果写成 dist[v] = graph[u][v] 而不比较大小，可能会把原来的更短距离覆盖掉，导致结果错误。
忘记标记已访问：如果不标记已访问，算法会重复选择同一个顶点，形成循环错误。
邻接矩阵中忘记对角线为0，无边为 INF：对角线表示自己到自己的距离，应该是0；无边的格子应该设置为一个很大的数（如 INT_MAX）。

完整的 C++ 代码运行示例

下面用邻接矩阵实现 Prim 算法，代码中有详细中文注释，方便理解。

#include <iostream>
#include <vector>
#include <climits> // 用来获取 INT_MAX
using namespace std;

const int INF = INT_MAX; // 表示无穷大，表示两个顶点之间没有直接边

/**
 * 计算最小生成树的总权值
 * @param n 顶点数量（村庄数量）
 * @param graph 邻接矩阵，graph[i][j] 表示顶点 i 到 j 的边权（成本）
 * @return 最小生成树的总权值，如果图不连通返回 -1
 */
int prim(int n, vector<vector<int>> &graph) {
    vector<bool> visited(n, false);   // 记录顶点是否已访问（已加入树）
    vector<int> dist(n, INF);         // 每个顶点到当前树的最短距离
    dist[0] = 0;                      // 从顶点0（第一个村庄）开始，自己到自己的距离为0
    int totalWeight = 0;              // 最小生成树的总权值

    for (int i = 0; i < n; i++) {     // 需要加入 n 个顶点
        // 1. 在未访问的顶点中，找 dist 最小的那个
        int u = -1;
        int minDist = INF;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                u = j;
            }
        }
        // 如果找不到符合条件的顶点，说明图不连通
        if (u == -1) {
            cout << "图不连通，无法构造最小生成树" << endl;
            return -1;
        }
        // 2. 将该顶点加入树
        visited[u] = true;
        totalWeight += minDist;       // 加上这条边的权值

        // 3. 更新它的邻居到树的最短距离
        for (int v = 0; v < n; v++) {
            // 如果 v 未访问，并且从 u 到 v 有边，且这条边的权值比当前 dist[v] 更小
            if (!visited[v] && graph[u][v] < dist[v]) {
                dist[v] = graph[u][v]; // 更新为更短的距离
            }
        }
    }
    return totalWeight;
}

int main() {
    // 村庄数量
    int n = 5;
    // 邻接矩阵，表示5个村庄之间的修路成本
    // 0表示自己到自己，INF表示没有直接路
    vector<vector<int>> graph = {
        {0, 2, INF, 6, INF},
        {2, 0, 3, 8, 5},
        {INF, 3, 0, INF, 7},
        {6, 8, INF, 0, INF},
        {INF, 5, 7, INF, 0}
    };
    int result = prim(n, graph);
    if (result != -1) {
        cout << "最小生成树的总成本: " << result << endl;
    }
    return 0;
}

运行结果：

最小生成树的总成本: 16

代码关键点说明

graph[u][v] 表示村庄 u 到 v 的直接修路成本。如果成本为 INF，表示两个村庄之间没有直接路。
dist 数组随着算法的进行不断更新：每加入一个新村庄，检查它能否让其他未加入的村庄离树更近。
总成本 totalWeight 在每轮加入村庄时累加 minDist，这个 minDist 正是新加入的那条边的权值。
如果图不连通（例如有些村庄与世隔绝），算法会返回 -1 并给出提示。

另一种生活例子：学校连接电脑

假设学校有5个办公室，每个办公室之间可以拉网线（成本不同，有高有低）。现在想让所有办公室都能互相通信，并且总网线长度最短。Prim 算法的做法就是：先从办公室0开始，拉一根最短的网线到最近的办公室1；然后从办公室0和1组成的网络中，拉一根最短的网线到下一个最近的办公室……直到所有办公室都连上网。最终得到的网络就是最小生成树。

与 Kruskal 算法的对比

Prim 算法：从点出发，每次选离当前树最近的边，像滚雪球。适合稠密图（边很多），用邻接矩阵实现较慢但简单。
Kruskal 算法：从边出发，每次选全局最短的边，如果不会形成环就加入。适合稀疏图（边少），通常用并查集实现。

两种算法都能得到最小生成树的总权值，但思路不同。