Prim算法在C++中需用优先队列配合邻接表实现，因std::priority_queue不支持decrease-key，采用重复入队+visited标记；邻接表宜用vector<pair<int,int>>；需自定义小根堆比较器；边记录为{u,v,w}；不连通图应报错；稠密图宜改用O(V²)数组版。
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, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
-
a.first > b.first是关键：优先队列“认为”a优先级更低时才把它压到下面，所以反着写 - 如果用结构体，记得重载
operator<并返回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<0>(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()会出错
真正写代码时，得先判断图密度再选策略；很多教程只讲堆版，但生产环境里稠密图用数组版才是常态。
