首页 > 编程语言 >C++实现最小生成树Prim算法 _ 邻接矩阵与贪心策略【源码】

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

来源：互联网 2026-04-18 18:05:05

邻接矩阵实现Prim算法的核心逻辑使用邻接矩阵实现Prim算法，其核心思路非常直观：通过一个二维数组 graph[i][j] 存储每对顶点之间的边权。整个过程类似于一棵树从起点开始“生长”。在每一步中，算法都从已构成的“树”出发，向外选择一条最短的边，从而将一个全新的顶点纳入树中。理解此算法的关

邻接矩阵实现Prim算法的核心逻辑

使用邻接矩阵实现Prim算法，其核心思路非常直观：通过一个二维数组 graph[i][j] 存储每对顶点之间的边权。整个过程类似于一棵树从起点开始“生长”。在每一步中，算法都从已构成的“树”出发，向外选择一条最短的边，从而将一个全新的顶点纳入树中。

理解此算法的关键在于明确 minDist[] 数组的含义。许多初学者容易将其与Dijkstra算法中的距离数组混淆。minDist 记录的并非某个顶点到源点的最短路径长度，而是每个尚未加入生成树的顶点，到当前“已选顶点集合”所构成子树的最短距离。换言之，对于任意未被选中的顶点v，我们关注的是它到树中任意顶点所有边中权值最小的那条。

长期稳定更新的攒劲资源： >>>点此立即查看<<<

具体操作上，通常将起点的 minDist 初始化为0，其他顶点则设为无穷大（INF）。之后，每当选中一个距离最小的顶点 u 加入生成树，紧接着就需要执行关键步骤：遍历所有未被访问的顶点 v，检查通过新加入的顶点 u 能否缩短它们到树的距离。即执行更新操作：minDist[v] = min(minDist[v], graph[u][v])。这一更新步骤是贪心策略得以正确推进的根本保证。

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

避免邻接矩阵Prim算法中的常见错误

邻接矩阵的实现方式虽然结构清晰，但也存在一些典型的“陷阱”。第一个常见问题是下标混淆。题目给定的顶点编号通常从1开始，而程序中的数组索引默认从0开始。如果在读入边权时忘记进行 u--; v--; 这样的转换，后续所有操作都会发生错位。

更为隐蔽的逻辑错误常出现在更新 minDist 的过程中。在邻接矩阵中，若两个顶点之间没有边相连，通常用0或一个特定的 INF 值表示。如果在更新时未判断 graph[u][v] 是否有效（即是否为 INF 或0，取决于具体定义），就可能将一条不存在的边误认为候选边，从而污染整个距离数组。

要有效避开这些陷阱，可以养成以下实用的编码习惯：

统一索引规范：在输入完成后，第一时间将顶点编号转换为以0为起始。
更新前进行校验：在尝试用 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之间的边权，而非历史上所有已选顶点。这种贪心选择的局部最优性，正是构成全局最优解的基础。一旦这一逻辑链条出错，整个算法便会失效。

侠游戏发布此文仅为了传递信息，不代表侠游戏网站认同其观点或证实其描述