不必。Prim算法不要求边权为正数，其正确性基于贪心选择性质与MST割性质，负权边不影响已选顶点到未选顶点的最小距离更新；priority_queue实现时需用小顶堆（如greater），并注意初始化、vis标记和松弛条件。
Prim算法用priority_queue实现时，边权必须是正数吗？
必须是。Prim本质是贪心，每次选离当前树最近的点，如果存在负权边，已加入MST的点可能被后续更小的负权边“拉回来”，破坏贪心选择性质。实际写代码时，priority_queue默认大顶堆，得用greater或自定义比较器，否则会把最大距离弹出来。
常见错误现象：priority_queue漏写模板参数第三项，编译报错；或者边权传反（把weight, to写成to, weight），导致取错节点。
- 初始化：所有点距离设为
INT_MAX，起点距离=0，入队{0, start} - 访问标记用
vector，出队后立刻vis(n, false) vis[u] = true，避免重复处理 - 松弛操作只对
!vis[v]的邻接点做，且仅当weight 才更新并入队
Kruskal算法里，并查集路径压缩不写find(x) = find(parent[x])会怎样？
会超时。不压缩时，最坏情况下find退化为O(n)，Kruskal整体从O(m log m)掉到O(mn)。尤其在稠密图或链状结构测试用例（如UVA 10600）中，不压直接TLE。
使用场景：边数m远小于点数n²时更优，比如稀疏网络拓扑、带地理坐标的点集连边。
sort(edges.begin(), edges.end(), [](const auto& a, const auto& b) { return a[2] ——按权排序，别漏[2]（假设存为{u, v, w}）- 并查集
parent数组初始化为i，不是-1（除非你写的是带秩合并+负数标记版） - 合并前务必
if (find(u) != find(v))，否则成环
用邻接表存图跑Prim，vector>>和vector>哪种更稳？
前者更稳。C++中pair是标准类型，无构造/析构开销，内存连续，push_back不会触发意外拷贝。而自定义struct edge { int to, w; }若没写移动构造，在频繁入队时可能多一次复制。
性能影响：实测百万边规模下，pair比轻量struct快约3%～5%，主要省在模板实例化和内联优化上。
- 邻接表索引从0开始，确保
graph[u].emplace_back(v, w)中u和v没越界 - 无向图记得双向加边：
graph[u].emplace_back(v, w); graph[v].emplace_back(u, w); - 如果输入含重边，Prim不受影响，但Kruskal需提前去重或靠排序+跳过处理
LeetCode 1135这类题输出最小花费，但图不连通怎么办？
返回-1。两种算法都需检查最终生成树边数是否等于n - 1。Prim看vis中true个数，Kruskal看cnt_edge计数器。别依赖“算法自然失败”——Prim可能停在某个子图里不动，Kruskal则只是边加不满就结束。
容易踩的坑：输入含孤立点（度为0），此时n=5但只有4个点能连通，仍要返回-1；另外，判断连通性不能只看原图DFS/BFS，因为权重会影响选边结果。
- Prim结束后，循环检查
for (int i = 0; i - Kruskal中每成功合并一次，
cnt_edge++，最后if (cnt_edge != n - 1) return -1; - 注意题目是否允许自环或重边，
if (u == v)应跳过，避免污染并查集
实际写的时候，负权边、不连通、重边、索引越界这四类问题占调试时间八成以上。算法逻辑本身很薄，难的是边界兜底。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
