C++实现最小生成树Prim算法 _ 邻接矩阵与贪心策略【源码】

Prim算法在邻接矩阵上的核心逻辑是什么

用邻接矩阵来实现Prim算法，其核心思路其实很直观：用一个二维数组 graph[i][j] 来存储每对顶点之间的边权。整个过程，就像是让一棵树从起点开始“生长”。每次，我们都从已经长成的“树”上，向外探出一条最短的边，把一个新的顶点“拉”进来。

这里的关键，在于理解 minDist[] 这个数组的真正含义。很多朋友容易把它和Dijkstra算法里的距离数组搞混。它记录的，并不是某个顶点到源点的最短路径长度，而是每个尚未加入生成树的顶点，到当前这棵“已选集合树”的最近距离。换句话说，对于任意一个还没被选中的顶点v，我们关心的是它到树中任意一个顶点的所有边里，权值最小的那条。

具体操作上，通常把起点对应的 minDist 初始化为0，其他顶点设为无穷大（INF）。之后，每当我们选中一个距离最小的顶点 u 加入生成树，紧接着就要做一件事：遍历所有未被访问的顶点 v，看看通过新加入的 u 这条边，能不能让它们离这棵树“更近”一点。也就是执行 minDist[v] = min(minDist[v], graph[u][v])。这个更新动作，才是贪心策略得以正确推进的保证。

如何避免邻接矩阵Prim中的典型越界与逻辑错位

邻接矩阵的实现虽然结构清晰，但“坑”也不少，稍不注意就会掉进去。第一个常见问题是下标混淆。题目给的顶点编号习惯从1开始，但我们的数组索引是从0开始的。如果读入边权时忘记做 u--; v--; 这样的转换，后续所有操作都会错位。

更隐蔽的逻辑错误，往往出在更新 minDist 的时候。邻接矩阵中，两个顶点之间没有边，通常会用0或者一个特定的 INF 值来表示。如果在更新时没有判断 graph[u][v] 是否有效（即是否为 INF 或0，取决于你的定义），就可能把一条不存在的边当作候选边，从而污染了整个距离数组。

要避开这些陷阱，有几个实用的编码习惯值得养成：

• 统一索引：输入完成后，第一时间将顶点编号转为0-based。
• 更新前校验：在尝试用 graph[u][v] 更新 minDist[v] 前，务必加上条件判断：if (graph[u][v] != INF && !visited[v])。
• 防溢出初始化：将 INF 定义为 INT_MAX / 2 而非 INT_MAX。这是因为后续有加法比较操作（minDist[v] = min(minDist[v], graph[u][v])），直接用最大值可能导致整数溢出。
• 全局扫描：在寻找下一个待加入顶点时，循环必须遍历所有n个顶点。在邻接矩阵的实现里，没有“邻接点”的概念，每个未访问的顶点都是潜在的候选者。

邻接矩阵Prim的时间复杂度与何时该换邻接表

邻接矩阵版Prim算法的时间复杂度是稳定的 O(n²)。原因很简单：外层循环要选n个顶点，内层则需要进行两次全量扫描——一次是找出 minDist 最小的顶点，另一次是用新加入的顶点更新所有其他顶点的 minDist。

那么，什么时候该用这个版本呢？答案是：稠密图。当边的数量 m 非常接近顶点数 n 的平方时（比如网格图、完全图），O(n²) 的复杂度是可以接受的，甚至因为其实现简单、常数小，反而有优势。

但是，如果面对的是稀疏图（比如社交网络的关系子图，m 远小于 n²），继续使用邻接矩阵就很不划算了。此时，邻接表配合优先队列（堆）优化的Prim算法，可以将复杂度降至 O(m log n)。当n达到10^4这个量级时，O(n²) 的一亿次操作和 O(m log n) 的几十万次操作，性能差距是数量级的。

一个简单的判断原则是：如果 m > n * n / 4，可以优先考虑邻接矩阵；否则，果断选择邻接表实现。千万别被邻接矩阵代码简短的表象所迷惑，在错误的数据规模上，再优雅的代码也会变得异常缓慢。

一个可直接运行的邻接矩阵Prim模板（含输入校验）

理论说再多，不如一个健壮的代码模板来得实在。下面这个版本，重点考虑了边界情况和错误处理，变量命名也力求清晰：

#include 
#include 
#include 
#include 
using namespace std;

const int INF = INT_MAX / 2;

int prim(const vector>& graph, int n) {
    vector minDist(n, INF);
    vector visited(n, false);
    minDist[0] = 0;
    int totalWeight = 0;

    for (int i = 0; i < n; ++i) {
        // 1. 找出当前未访问顶点中，距离已选集合最近的那个
        int u = -1;
        for (int v = 0; v < n; ++v) {
            if (!visited[v] && (u == -1 || minDist[v] < minDist[u])) {
                u = v;
            }
        }

        // 如果找不到，或者最近距离仍是INF，说明图不连通
        if (u == -1 || minDist[u] == INF) {
            return -1;
        }

        visited[u] = true;
        totalWeight += minDist[u];

        // 2. 用新加入的顶点u，更新其他未访问顶点的最小距离
        for (int v = 0; v < n; ++v) {
            if (!visited[v] && graph[u][v] != INF) {
                minDist[v] = min(minDist[v], graph[u][v]);
            }
        }
    }
    return totalWeight;
}

使用前需要注意：传入的 graph 必须是一个 n x n 的方阵。对于无向图，务必保证 graph[u][v] = graph[v][u] = weight 的对称赋值。函数返回 -1 表示图不连通，无法生成最小生成树——这个检查在生产环境中至关重要，很多测试只跑连通图，一旦遇到孤立顶点，程序就可能产生未定义行为。

最后，真正理解这个算法的精髓，在于记住那个动态更新的依赖关系：每次更新 minDist[v]，依据的仅仅是刚刚加入的顶点u 与v之间的边权，而不是历史上所有已选顶点。这个贪心选择的局部最优性，正是构成全局最优解的基础，一旦这个逻辑链条出错，整个算法就失效了。