Prim算法核心是贪心扩展:从任一顶点出发,每次选距当前生成树最近的未访问顶点加入,维护dist[]数组记录最短边权;需及时更新dist[]、避免重复选点;图不连通时算法提前终止,应检查visited数组是否全为true。

Prim算法的核心思想是“贪心扩展”
它从任意一个顶点开始,每次把离当前生成树最近的未访问顶点加进来,逐步撑起一棵树。关键不在于“找全局最小边”,而在于维护一个动态的距离数组 dist[],记录每个未加入顶点到已建树的最短边权。
实现时最容易卡在两点:一是没及时更新 dist[],二是误把已加入顶点重复选入。C++里用 vector 存图、priority_queue 加速找最小距离顶点更稳妥,但要注意 priority_queue 默认大根堆,得用 greater 或负权技巧。
- 邻接表推荐用
vector:外层下标是起点,内层>> pair -
dist[v]初始设为INT_MAX,起点设为 0;用visited[v]标记是否已入树 - 每次从候选集中取
dist[u]最小的u,再遍历其所有邻边v,若!visited[v] && weight ,就更新dist[v] = weight
用 priority_queue 实现 O(E log V) 时间复杂度
手动维护最小堆比每次线性扫描 dist[](O(V²))高效得多,尤其图稀疏时。但 C++ 的 priority_queue 不支持减键操作,所以采用“懒删除”策略:插入新距离时不管旧值,只在出队时检查 dist[u] 是否已过期。
典型写法是存三元组 {dist[u], u, edge_weight},但实际只需前两个——因为边权已在图结构里存好。注意比较逻辑:
priority_queue<pair int>, vector<pair int>>, greater<pair int>>> pq;
// {dist[u], u},靠 first 升序排列
</pair></pair></pair>
- 每次
pq.push({dist[u], u})后,不删旧项;出队时若dist[u] != current_dist就跳过 - 更新
dist[v]后必须pq.push({dist[v], v}),否则新距离不会被考虑 - 边权为负会导致 Prim 失效——Prim 要求权值非负,这点常被忽略
邻接矩阵版适合稠密图,但要注意初始化陷阱
如果用二维数组 graph[V][V] 存图,graph[i][j] == 0 可能被误认为“无边”,其实应设为 INT_MAX 表示无穷大。初始化阶段漏掉这个,会导致错误地把 0 当作有效边权参与松弛。
- 输入边时,对无向图要双向赋值:
graph[u][v] = graph[v][u] = w; -
dist[]初始全为INT_MAX,dist[0] = 0(起点任选) - 每次循环找最小
dist[i]且!visited[i]的i,再用它更新所有j满足graph[i][j] != INT_MAX - 矩阵版空间 O(V²),V > 1e4 就容易爆内存,别硬套
如何验证结果正确性?别只看总权重
输出的 total_weight 对不上预期,未必是算法错——更可能是图没连通或输入格式有坑。Prim 只对连通图有效,若图不连通,算法会提前结束,visited 数组里仍有 false 项。
- 运行完检查
count_if(visited.begin(), visited.end(), [](bool b){return b;}) == V - 打印每条加入的边(起点、终点、权值),对照手算的小样例(如 4 点 5 边)逐条核对
- 若用
double权值,注意浮点比较别用==,改用fabs(a - b) - 重边处理:邻接表自然保留最小那条;邻接矩阵需在输入时做
min(graph[u][v], w)
实际写的时候,边界判断和初始化比主循环还容易出错。尤其是 dist 数组初值、visited 清零、以及 priority_queue 中重复节点的过滤逻辑——这三处漏一个,结果就完全不对。
C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!











