c++如何实现Prim算法最小生成树_c++ 邻接矩阵与贪心策略选择【实战】

Prim算法用邻接矩阵实现需初始化key[0]=0、其余INT_MAX，每次选未入树且key最小的顶点u，再更新其邻接点v的key和parent；贪心正确性源于MST切割性质，支持负权边，时间复杂度O(n²)，稠密图适用，但需避免0误判无边、索引错位及状态残留。

Prim算法在C++中用邻接矩阵怎么写

邻接矩阵是Prim算法最直观的实现方式，尤其适合顶点数不多（比如 n ≤ 1000）的稠密图。核心思路是维护一个key[]数组记录每个顶点到当前生成树的最小边权，再用inMST[]标记是否已加入生成树。

关键点不是“能不能写”，而是初始化和更新逻辑容易出错：比如key[0]必须设为0（从顶点0开始），其余初始化为INT_MAX；每次选key最小且未入树的顶点时，必须检查!inMST[u]，否则会重复选取。

vector> graph = {
    {0, 2, 0, 6, 0},
    {2, 0, 3, 8, 5},
    {0, 3, 0, 0, 7},
    {6, 8, 0, 0, 9},
    {0, 5, 7, 9, 0}
};
int n = graph.size();
vector key(n, INT_MAX);
vector inMST(n, false);
vector parent(n, -1);

key[0] = 0;

for (int i = 0; i < n; i++) {
    int u = -1;
    for (int j = 0; j < n; j++)
        if (!inMST[j] && (u == -1 || key[j] < key[u]))
            u = j;
    
    inMST[u] = true;
    for (int v = 0; v < n; v++)
        if (graph[u][v] != 0 && !inMST[v] && graph[u][v] < key[v]) {
            key[v] = graph[u][v];
            parent[v] = u;
        }
}

为什么贪心选择“当前最小边”不会错过全局最优

Prim的贪心正确性依赖于MST的切割性质（cut property）：对任意切割，横跨该切割的最小权重边一定属于某棵MST。算法每一步都在维护一个已构建的子树集合S，把V\S看作另一侧——此时连接S与V\S的最小边必然可安全加入。

• 这个性质不依赖边权是否为正，但要求图连通；若不连通，key[v]最终仍为INT_MAX，可据此判断
• 如果图含负权边，Prim依然成立（不同于Dijkstra），因为不涉及路径累加，只比单条边权
• 但邻接矩阵中用0表示无边时，必须确保真实边权≠0；否则要改用-1或INT_MAX作无效标记

邻接矩阵Prim的时间复杂度和优化边界

标准实现是O(n²)：外层循环n次，每次找最小key耗O(n)，更新邻居也耗O(n)。这比堆优化版（O(m log n)）在稀疏图中慢，但在稠密图（m ≈ n²）下两者接近，且邻接矩阵常数更小、代码更稳。

立即学习“C++免费学习笔记（深入）”；

Copilot

Copilot是由微软公司开发的一款AI生产力工具，旨在通过先进的人工智能技术，帮助用户快速完成各种任务，提升工作效率。

下载

真正要注意的是内存和初始化开销：

• graph二维vector大小为n × n，n=10⁴时就需约400MB内存（int占4字节），直接爆掉
• 若实际边数很少，强行用邻接矩阵纯属浪费；应切到邻接表+priority_queue
• 初始化key用vector(n, INT_MAX)没问题，但别用memset(key, 0x3f, sizeof(key))——它按字节赋值，对int可能不等于0x3f3f3f3f

调试时最常见的三个错误现象

写完跑不对？先盯这三个地方：

• 邻接矩阵中用0表示“无边”，但某条合法边权恰好是0 → 更新时if (graph[u][v] != 0)会跳过它。解决：统一用-1或INT_MAX作无效标记，或额外存valid标志
• parent[v] = u写成parent[u] = v → 最终输出的边反向，生成树结构错乱
• 没重置inMST或key就复用同一组变量跑多组数据 → 上一轮残留状态污染结果

邻接矩阵Prim看似简单，但初始化语义、无效值约定、索引方向这三点，几乎包揽了90%的本地调试失败原因。