C++如何计算图的最小生成树（Prim算法）-C++-PHP中文网

prim算法在c++中需用优先队列配合邻接表实现，因std::priority_queue不支持decrease-key，采用重复入队+visited标记；邻接表宜用vector；需自定义小根堆比较器；边记录为{u,v,w}；不连通图应报错；稠密图宜改用o(v²)数组版。

c++如何计算图的最小生成树（prim算法）

Prim算法在C++中需要优先队列和邻接表配合

Prim算法本质是贪心，每次选离当前生成树最近的未访问节点。C++标准库没有现成的“带权边更新”的优先队列，std::priority_queue不支持降低键值（decrease-key），所以不能直接套用教科书伪代码。实际做法是允许重复入队，靠访问标记跳过已处理节点——这会略微增加堆大小，但实现简单且时间复杂度仍是 O((V+E) log V)。

邻接表用 vector<vector int>>></vector> 最合适：外层索引是顶点编号，内层每个 pair<to weight></to> 存邻边。别用 map 或 unordered_map 做邻接结构，除非顶点编号稀疏且非连续。

初始化时把起点（比如0）连向自身的边（权重0）推入队列：pq.push({0, 0})
维护一个 vector<bool> visited</bool> 标记是否已加入MST，避免重复处理
每次 pq.top() 取出后先检查 visited[u]，为真就 continue
权重类型建议统一用 int 或 long long，避免混合类型隐式转换出错

手写比较器让priority_queue按权重升序排列

std::priority_queue 默认是大根堆，而Prim需要最小权重优先，所以必须自定义比较器。常见错误是写成 greater<pair>></pair>，但这会先比第一个元素（权重），再比第二个（节点），导致相同权重时顺序不可控，可能影响正确性（虽不影响最终结果，但调试困难）。

稳妥写法是显式定义结构体或lambda，只按权重比较：

C++

"空空如也"

下载

auto cmp = [](const pair<int int>& a, const pair<int int>& b) {
    return a.first > b.first; // 小根堆：权重小的优先级高
};
priority_queue<pair int>, vector<pair int>>, decltype(cmp)> pq(cmp);</pair></pair></int></int>

a.first > b.first 是关键：优先队列“认为”a优先级更低时才把它压到下面，所以反着写
如果用结构体，记得重载 operator 并返回 <code>false 表示“不小于”，逻辑容易绕，lambda更直白
不要把节点编号放 first、权重放 second，否则比较器要多一层解包，易错

Prim输出MST边集时容易漏掉起始边

算法过程中，每次从队列取出一个节点 u，并遍历其所有邻接边 (u, v, w)。只有当 v 未被访问过时，才把 v 和边权 w 加入MST。但注意：这条边的两个端点是 u 和 v，而 u 是刚被确认加入MST的节点，v 是新加入的——所以记录边时应存 {u, v, w}，不是 {v, u, w}（虽然无向图等价，但调试时方向混乱会干扰判断）。

起点没有“前驱边”，所以MST边数一定是 V-1 条，循环里计数器到 V-1 就该停，别依赖队列为空
如果图不连通，visited 中会有未标记节点，此时应提前报错，而不是静默返回不完整结果
边集用 vector<tuple int>></tuple> 存，比嵌套 vector 更清晰；打印时用 get(e) 等取值，避免下标魔法数字

稠密图用邻接矩阵+数组优化比堆更快

当边数 E ≈ V²（比如完全图），堆操作的 log V 开销变得显著，此时改用朴素Prim：用数组 minEdge[i] 记录节点 i 到当前MST的最短边权，每次 O(V) 扫描找最小值，总复杂度 O(V²)，反而比堆版快。

初始化 minEdge 全为 INT_MAX，minEdge[0] = 0
每轮找未访问节点中 minEdge[u] 最小的那个，将其标记为已访问，并累加权重
然后用 u 更新所有邻接点 v 的 minEdge[v] = min(minEdge[v], weight[u][v])
邻接矩阵用 vector<vector>></vector>，注意初始化时对角线为0、无边处填 INT_MAX，别用 -1——否则 min() 会出错