Prim算法最合理用priority_queue（最小堆）配合邻接表，时间复杂度降至O((V+E)logV)，显著优于邻接矩阵的O(V²)，尤其适合稀疏图；需用visited数组判重，避免同一节点多次处理，且pair必须权重在前以确保正确排序。
Prim算法在C++中用什么数据结构最合理
用priority_queue（最小堆）配合邻接表是主流选择，比朴素O(V²)实现快得多，尤其适合稀疏图。手写二叉堆或用std::priority_queue<:pair int>></:pair>（权重在前，节点在后）能自然支持“当前最小边”弹出。别用set模拟堆——插入/删除虽是log，但priority_queue常数更小，且不需要支持中间元素修改。
常见错误：把pair顺序写反，导致堆按节点ID排序而非权重，结果完全错误。正确写法是priority_queue<pair int>, vector<pair int>>, greater<pair int>>></pair></pair></pair>，或直接存{weight, node}并用greater。
如何避免重复加入已访问节点
Prim的核心是维护一个“已入树节点集合”，每次只从该集合向外拓展一条最小边。必须用布尔数组visited[]或vector<bool></bool>标记，不能仅靠堆里有没有来判断——因为同一节点可能被多次压入堆（不同路径到达），但只有第一次弹出时才有效。
实操要点：
立即学习“C++免费学习笔记（深入）”；
- 初始化时只将起点（如0号节点）入堆，
visited[0] = true - 每次
pop后先检查if (visited[node]) continue;，再处理 - 扩展邻居时，只对
!visited[nbr]的节点压入堆
边权为负数时Prim还能用吗
可以，只要图连通且无向。Prim不依赖边权非负——它只比较大小，不作松弛更新。这点和Dijkstra有本质区别。但要注意：若存在负权环（虽然无向图中负权边本身就会构成“环”，但Prim不关心环），只要图是简单连通无向图，算法逻辑依然成立。
不过实际中极少遇到负权MST场景；若真有，确认输入图确实是无向的，且adj[u].push_back({v, w})和adj[v].push_back({u, w})都加了，否则会误判连通性。
完整代码里最容易漏掉的三件事
写完常跑不对？大概率栽在这三个地方：
- 没初始化
visited数组，所有元素默认为false看似安全，但若用vector<bool> visited(n)</bool>而n=0，访问visited[0]就越界 - 堆中存的是
{weight, node}，但遍历时误把weight当node去访问邻接表，比如写成for (auto [w, v] : adj[weight]) - 没累计总权重，或把某条边权加了两次（一次在压堆时，一次在弹出时）——只应在
!visited[node]成功加入树时加一次
边界情况比想象中多：节点数为1时，循环不进，得单独返回0；图不连通时，最终count ，应报错或返回非法值。这些不显式处理，调试时很难定位。
