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

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

使用邻接矩阵实现Prim算法，其核心思想非常清晰：通过一个二维数组 graph[i][j] 来存储图中每对顶点之间的边权值。整个过程，可以形象地理解为一棵最小生成树从指定的起点开始“生长”。在每一轮迭代中，算法都会从当前已构成的“树”上，向外延伸一条权值最小的边，从而将一个全新的顶点“纳入”生成树集合。

免费影视、动漫、音乐、游戏、小说资源长期稳定更新！ 👉 点此立即查看 👈

理解此算法的关键，在于准确把握 minDist[] 数组的真实定义。许多初学者容易将其与Dijkstra算法中的距离数组混淆。实际上，它记录的并非某个顶点到源点的最短路径长度，而是每个尚未加入生成树的顶点，到当前“已选顶点集合”（即生成树）的最近距离。更具体地说，对于任意一个待选顶点v，我们关注的是它到树中所有顶点之间的边中，权值最小的那一条边的权重。

在具体操作步骤上，通常将起点的 minDist 初始化为0，其余顶点则设置为一个极大值（INF）。之后，每当我们选择当前 minDist 值最小的顶点 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起始（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模板（含输入校验）

理论阐述再多，不如一个健壮、可直接使用的代码模板来得实用。下面提供的这个C++版本，重点考虑了边界情况和错误处理，变量命名也力求清晰易懂：

#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 时，表示图不连通，无法生成最小生成树——这项检查在实际应用和算法题解中至关重要，许多测试用例可能包含孤立顶点，缺乏此检查将导致程序产生未定义行为或错误结果。

最后，深刻理解Prim算法的精髓，在于牢记其动态更新的依赖关系：每次更新 minDist[v] 时，依据的仅仅是刚刚加入的顶点u 与顶点v之间的边权，而非历史上所有已选顶点。这种基于局部最优的贪心选择，正是构成全局最优解的基础。一旦这个核心逻辑链条出错，整个算法将无法得到正确的最小生成树。