prim算法在邻接矩阵上的核心逻辑是维护mindist[]数组记录各未选顶点到已选集合的最小边权，每次选mindist最小顶点u，用graphu更新未访问v的mindist[v]。
Prim算法在邻接矩阵上的核心逻辑是什么
邻接矩阵实现Prim，本质是用二维数组 graph[i][j] 存储边权，每次从已选顶点集向外“探出一条最短边”。关键不在于堆优化，而在于维护一个 minDist[] 数组——它记录每个未加入树的顶点到当前生成树的**最近距离**，不是到某个固定源点的距离。
常见错误是把 minDist[v] 误解为“从起点到v的最短路径”，实际它是“v到已选集合中任意顶点的最小边权”。初始化时除起点外全设为 INF，起点设为0；之后每选一个新顶点 u，就遍历所有未访问顶点 v，用 graph[u][v] 更新 minDist[v] = min(minDist[v], graph[u][v])。
如何避免邻接矩阵Prim中的典型越界与逻辑错位
邻接矩阵下标从0开始，但初学者常混淆顶点编号和数组索引，尤其在读入边时没做-1转换。更隐蔽的问题是：更新 minDist 时漏判 graph[u][v] == 0（无边）或 graph[u][v] == INF（不连通），导致把无效边当作候选边参与比较。
- 读入边后务必统一转为0-based索引：
u--; v--; - 更新
minDist[v]前加判断：if (graph[u][v] != INF && !visited[v]) -
minDist初始值必须大于所有可能边权，建议用INT_MAX / 2而非INT_MAX，防止后续minDist[v] = min(minDist[v], graph[u][v])溢出 - 找下一个加入顶点时，循环必须覆盖全部
n个顶点，不能只扫邻接点——邻接矩阵里“邻接”是隐式的
邻接矩阵Prim的时间复杂度与何时该换邻接表
纯邻接矩阵Prim是 O(n²)：外层循环 n 次，内层找最小值和更新各扫一遍 n 元素。它适合稠密图（m ≈ n²），比如网格图、完全图；但若图稀疏（m ），比如社交网络抽样子图，用邻接表+堆能压到 <code>O(m log n)，此时硬套邻接矩阵会慢几倍甚至几十倍。
实操判断标准：if (m > n * n / 4) 可考虑邻接矩阵；否则优先写邻接表版本。别被“代码短”误导——稀疏图上 O(n²) 的常数再小也扛不住 n=10⁴ 时的一亿次操作。
一个可直接运行的邻接矩阵Prim模板（含输入校验）
下面是最简可用版本，重点在边界防护和变量命名直白：
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
<p>const int INF = INT_MAX / 2;</p>
<p>int prim(const vector<vector>>& graph, int n) {
vector<int> minDist(n, INF);
vector<bool> visited(n, false);
minDist[0] = 0;
int totalWeight = 0;</bool></int></vector></p>
<pre class="brush:php;toolbar:false;">for (int i = 0; i < n; ++i) {
// 找未访问中 minDist 最小的顶点
int u = -1;
for (int v = 0; v < n; ++v) {
if (!visited[v] && (u == -1 || minDist[v] < minDist[u])) u = v;
}
if (u == -1 || minDist[u] == INF) return -1; // 图不连通
visited[u] = true;
totalWeight += minDist[u];
// 用u更新所有未访问顶点
for (int v = 0; v < n; ++v) {
if (!visited[v] && graph[u][v] != INF) {
minDist[v] = min(minDist[v], graph[u][v]);
}
}
}
return totalWeight;
}
调用前确保 graph 是 n×n 方阵，无向图需对称赋值：graph[u][v] = graph[v][u] = weight;。返回 -1 表示不连通，这是生产环境必须检查的点——很多人只测连通样例，上线后遇到孤立点直接崩。
真正难的不是写对算法，而是记住：每次 minDist[v] 更新都依赖刚加入的 u，而不是历史所有已选点；这个依赖关系一旦错，整个贪心就失效了。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
