优先队列能优化prim算法，是因为它将每次查找最小dist[v]的时间从o(v)降至o(log v)，从而将总时间复杂度从邻接矩阵版的o(v²)优化为邻接表+堆的o(e log v)，显著提升稀疏图效率。
为什么优先队列能优化Prim算法
原始Prim用邻接矩阵+线性扫描找最小dist[v]，每次都要遍历所有顶点，时间复杂度固定为O(V²)。当图稀疏（E ）时，大量时间浪费在检查无边的顶点上。优先队列把“找最小距离顶点”从<code>O(V)降到O(log V)，配合邻接表只处理真实存在的边，整体变成O((V + E) log V)——这是真正可扩展的写法。
邻接表怎么建才适配优先队列版本
关键不是“能不能存”，而是“访问是否高效”。必须用vector<vector int>>></vector>：外层索引是起点顶点编号，内层pair存{权重, 目标顶点}。注意两点：
- 顶点编号建议从
1开始（避免0索引和边界混淆），初始化G.resize(V + 1) - 输入重边时必须取最小值：
G[u].push_back({min(w, existing_w), v})，否则松弛逻辑会出错 - 无向图要双向添加：
G[u].push_back({w, v}); G[v].push_back({w, u})
priority_queue的声明和入队逻辑容易错在哪
错误集中在比较规则和重复入队处理：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 必须用
greater<pair>></pair>，否则默认大根堆，取出来的是最大距离 - 不能只靠
push就认为顶点会被正确更新——同一顶点可能被多次push（比如先推{5, 3}，后发现更短路径又推{2, 3}） - 出队后必须立刻检查
if (isMST[u]) continue，跳过已处理过的旧记录，否则会重复松弛、甚至算错总权重 -
dist[u]只在入队前更新，入队内容是当时的dist[u]值，不是实时绑定
如何验证结果没漏顶点或连通性异常
优先队列版本不显式计数，容易忽略图不连通的情况：
- 循环结束后检查
isMST数组：若存在isMST[i] == false（i从1到V），说明图不连通，无法生成MST - 计算总权重时，不要直接累加
dist数组——起始点dist[1]是0，但其他点的dist[v]代表连向MST的那条边权，总和才是MST边权和 - 调试时打印
minHeap.size()和实际处理的顶点数，两者应趋近但不必相等（因有冗余入队）
最常被跳过的细节是：没有在push前判断!isMST[v]，导致无效边进堆，拖慢性能且增加内存占用。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
