Prim算法是解决带权无向图最小生成树问题的经典贪心算法。其核心思想是维护两个顶点集合：已加入生成树的集合U和未加入的集合V-U，每一步都从连接U与V-U的所有边中，选出权重最小的一条，将对应顶点纳入U。使用邻接矩阵存储图结构，能够用二维数组直观地表达任意两点间的边权，非常适合教学与稠密图场景。
一、邻接矩阵的定义与图初始化
在C++中，邻接矩阵通常用二维vector或原生数组表示。假设图有n个顶点，矩阵graph[i][j]存放顶点i到j的边权，若两点不直接相连则设为无穷大（如INT_MAX）。这种表示法让查询边权变为O(1)操作，但建图本身需要O(n^2)空间。
初始化时，我们要把对角线设为0，其他位置按输入或随机数据填充。下面代码展示了一个简单的矩阵构建方式，并演示了如何把不连通情况标记为大数，避免后续比较出错。
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
int n = 5;
// 用 vector 构建邻接矩阵
vector<vector<int>> graph(n, vector<int>(n, INT_MAX));
for (int i = 0; i < n; i++) {
graph[i][i] = 0; // 自己到自己的距离为0
}
// 假设输入边：0-1权2，0-3权6，1-2权3，1-3权8，1-4权5，2-4权7，3-4权9
graph[0][1] = graph[1][0] = 2;
graph[0][3] = graph[3][0] = 6;
graph[1][2] = graph[2][1] = 3;
graph[1][3] = graph[3][1] = 8;
graph[1][4] = graph[4][1] = 5;
graph[2][4] = graph[4][2] = 7;
graph[3][4] = graph[4][3] = 9;
return 0;
}
二、Prim算法的贪心策略与核心数组
Prim的贪心体现在“每一步都选当前可选的最小边”。为实现这一点，我们引入两个辅助数组：lowcost记录每个未入树顶点到已入树集合的最小边权，vis标记顶点是否已在生成树中。初始时，从顶点0开始，把lowcost[i]设为graph[0][i]，vis[0]置为true。
随后进行n-1轮循环：在每一轮中，扫描lowcost找到最小值对应的顶点u（要求vis[u]为false），将其加入生成树，然后以u为中介去“松弛”其他顶点——若graph[u][v]比当前lowcost[v]更小，就更新它。这种策略保证每次加入的边都是连接两集合的最小权重边，不会形成环。
void prim(vector<vector<int>>& graph, int n) {
vector<bool> vis(n, false);
vector<int> lowcost(n, INT_MAX);
// 从顶点0开始
vis[0] = true;
for (int i = 0; i < n; i++) {
lowcost[i] = graph[0][i];
}
int total = 0;
for (int cnt = 1; cnt < n; cnt++) {
int min_val = INT_MAX;
int u = -1;
for (int i = 0; i < n; i++) {
if (!vis[i] && lowcost[i] < min_val) {
min_val = lowcost[i];
u = i;
}
}
if (u == -1) {
cout << "图不连通，无法生成树" << endl;
return;
}
vis[u] = true;
total += min_val;
cout << "选择顶点 " << u << " 边权 " << min_val << endl;
// 松弛操作
for (int v = 0; v < n; v++) {
if (!vis[v] && graph[u][v] < lowcost[v]) {
lowcost[v] = graph[u][v];
}
}
}
cout << "最小生成树总权值: " << total << endl;
}
三、完整可运行示例与输出分析
将前面的初始化与prim函数组合，即可得到一份完整程序。以下代码在main中建图后直接调用prim，输出每次选中的顶点与累计权值，帮助理解贪心过程如何一步步覆盖全部节点。
对于上文的5顶点图，算法会依次选入顶点1（权2）、顶点2（权3）、顶点4（权5）、顶点3（权6），总权值为16。注意当图不连通时，u会保持-1，程序应及时退出并提示，否则会错误地把INT_MAX加入统计。
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
void prim(vector<vector<int>>& graph, int n) {
vector<bool> vis(n, false);
vector<int> lowcost(n, INT_MAX);
vis[0] = true;
for (int i = 0; i < n; i++) {
lowcost[i] = graph[0][i];
}
int total = 0;
for (int cnt = 1; cnt < n; cnt++) {
int min_val = INT_MAX;
int u = -1;
for (int i = 0; i < n; i++) {
if (!vis[i] && lowcost[i] < min_val) {
min_val = lowcost[i];
u = i;
}
}
if (u == -1) {
cout << "图不连通，无法生成树" << endl;
return;
}
vis[u] = true;
total += min_val;
cout << "选择顶点 " << u << " 边权 " << min_val << endl;
for (int v = 0; v < n; v++) {
if (!vis[v] && graph[u][v] < lowcost[v]) {
lowcost[v] = graph[u][v];
}
}
}
cout << "最小生成树总权值: " << total << endl;
}
int main() {
int n = 5;
vector<vector<int>> graph(n, vector<int>(n, INT_MAX));
for (int i = 0; i < n; i++) graph[i][i] = 0;
graph[0][1] = graph[1][0] = 2;
graph[0][3] = graph[3][0] = 6;
graph[1][2] = graph[2][1] = 3;
graph[1][3] = graph[3][1] = 8;
graph[1][4] = graph[4][1] = 5;
graph[2][4] = graph[4][2] = 7;
graph[3][4] = graph[4][3] = 9;
prim(graph, n);
return 0;
}
四、复杂度与实战注意事项
时间复杂度方面，外层循环n-1次，内层找最小和松弛各扫n个顶点，总体为O(n^2)。在顶点数不超过几千的稠密图中，这种实现比用优先队列的O(E log V)版本更简单且常数小。但若图很稀疏，邻接表加小根堆会更省时间。
实战中容易踩的坑包括：忘记把INT_MAX的边在松弛时参与比较导致溢出；用int存总权值在边权很大时越界；以及误把矩阵中0当成有效边（应区分自环0与初始化0）。建议将无穷大设为INT_MAX/2，避免加法溢出，并用long long累计权值。
| 存储方式 | 时间复杂度 | 适用场景 |
|---|---|---|
| 邻接矩阵+数组扫描 | O(V^2) | 稠密图、教学演示 |
| 邻接表+优先队列 | O(E log V) | 稀疏图、大规模数据 |
五、小结
用C++以邻接矩阵实现Prim算法，重点在于理解贪心选择靠lowcost数组落地，以及松弛步骤如何更新候选边。代码虽短，但边界处理决定了程序健壮性。掌握这一基础版本后，可进一步改写为堆优化形式应对不同数据规模。