Prim算法核心是贪心策略：从任一顶点出发，维护key[]（到生成树最短边权）和mstSet[]（是否已入树），每次选key最小未访问顶点并松弛邻接点；邻接矩阵实现需初始化key全为INT_MAX、起点为0，更新时须同时判断顶点未访问且边存在。
Prim算法的核心逻辑是什么
Prim算法从任意一个顶点出发，每次选择与当前生成树相连的、权值最小的边，把对应新顶点加入树中。关键不是“选边”，而是维护一个key[]数组（记录每个顶点到当前生成树的最短边权）和一个mstSet[]布尔数组（标记是否已入树）。它本质上是贪心 + 类Dijkstra的松弛过程。
用邻接矩阵实现Prim时要注意什么
邻接矩阵适合稠密图，代码简洁但时间复杂度为 O(V²)。容易出错的地方集中在三处：
-
key[]初始化必须全为INT_MAX，但起始点要设为0，否则第一个顶点无法被选中 - 更新
key[v]时，必须同时检查!mstSet[v]和graph[u][v] != 0（或），否则会误更新已加入的点或不存在的边 - 找最小
key[u]的循环里，必须跳过已加入的点（即mstSet[u]为true的情况），否则会重复选点
#include <iostream>
#include <climits>
using namespace std;
<p>void primMST(int graph[][5], int V) {
int parent[V];
int key[V];
bool mstSet[V];</p><pre class='brush:php;toolbar:false;'>for (int i = 0; i < V; i++) {
key[i] = INT_MAX;
mstSet[i] = false;
}
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V - 1; count++) {
int u = -1;
for (int v = 0; v < V; v++) {
if (!mstSet[v] && (u == -1 || key[v] < key[u]))
u = v;
}
mstSet[u] = true;
for (int v = 0; v < V; v++) {
if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}
for (int i = 1; i < V; i++)
cout << parent[i] << " - " << i << " \t" << graph[parent[i]][i] << endl;}
用邻接表 + 优先队列优化到 O(E log V)
稀疏图必须换邻接表+最小堆（priority_queue），否则超时。C++标准库的 priority_queue 默认是最大堆，得用 greater<pair<int, int>> 或取负；更稳妥的是自定义比较器。还要注意：堆里可能存着已失效的旧 key 值，所以每次 pop 后必须检查 mstSet[v]，跳过已处理的点。
立即学习“C++免费学习笔记（深入）”；
- 不要直接 push 新权值就完事，要 push
{weight, vertex}对 - 更新
key[v]后必须重新 push，不能修改堆中已有元素 - 图用
vector<vector<pair<int, int>>>存：外层索引是起点，内层是{终点, 权值}
常见报错和调试线索
运行时崩溃或结果错误，八成出在边界上：
- 输入邻接矩阵时行列数没对齐，比如传了
graph[5][4]却用V=5遍历第5行 → 越界访问 - 图不连通时，
key[v]保持INT_MAX，最后输出边权为大负数（整数溢出）→ 应提前检查是否存在key[v] == INT_MAX且!mstSet[v] - 使用
priority_queue时忘了加!mstSet[v]判断，导致同一顶点被多次加入生成树
最小生成树不一定唯一，只要总权值最小、边数等于 V-1、无环，就是正确解。验证时别只盯边顺序，重点看连通性和权值和。
