Prim算法从起始顶点出发，每次选择最近顶点加入生成树，利用贪心策略构建最小生成树。通过邻接矩阵存储图，用key数组记录各顶点到生成树的最短距离，mstSet标记已选顶点。初始化key为无穷大，起点key为0。循环中选取key最小且未访问的顶点u，将其加入MST，并遍历其邻接点v：若存在边(u,v)且v未访问且该边权重小于当前key[v]，则更新parent[v]=u和key[v]=graphu。最终输出每条MST边及权重，总时间复杂度O(V²)，适用于稠密图。示例图中MST总权值为16。
Prim算法用于在加权无向图中找出最小生成树（MST），即连接所有顶点且总权重最小的子树。C++中结合邻接矩阵实现该算法，逻辑清晰、便于理解。
Prim算法基本思想
从任意一个起始顶点开始，逐步将距离当前生成树最近的顶点加入集合，直到所有顶点都被包含。每次选择边权最小的边进行扩展，使用贪心策略保证整体最优。
关键点：
- 维护一个集合表示已加入生成树的顶点
- 用数组记录每个顶点到当前生成树的最短距离
- 每次选出未访问顶点中距离最小者，并更新其邻接点的距离
邻接矩阵存储图结构
使用二维数组graph[V][V]表示图，graph[i][j]为顶点i到j的边权。若无边，则设为一个极大值（如INT_MAX）。
立即学习“C++免费学习笔记（深入）”；
示例代码定义：
const int V = 5; // 顶点数
int graph[V][V] = {
{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0}
};
Prim算法实现步骤
以下是基于邻接矩阵的Prim算法完整实现：
#include#include using namespace std; int minKey(int key[], bool mstSet[]) { int min = INT_MAX, min_index; for (int v = 0; v < V; v++) if (!mstSet[v] && key[v] < min) min = key[v], min_index = v; return min_index; }
void printMST(int parent[], int graph[V][V]) { cout << "Edge \tWeight\n"; for (int i = 1; i < V; i++) cout << parent[i] << " - " << i << "\t" << graph[i][parent[i]] << endl; }
void primMST(int graph[V][V]) { int parent[V]; int key[V]; bool mstSet[V];
for (int i = 0; i zuojiankuohaophpcn V; i++) key[i] = INT_MAX, mstSet[i] = false; key[0] = 0; parent[0] = -1; for (int count = 0; count zuojiankuohaophpcn V - 1; count++) { int u = minKey(key, mstSet); mstSet[u] = true; for (int v = 0; v zuojiankuohaophpcn V; v++) if (graph[u][v] && !mstSet[v] && graph[u][v] zuojiankuohaophpcn key[v]) parent[v] = u, key[v] = graph[u][v]; } printMST(parent, graph);}
运行与输出说明
调用primMST(graph)后，程序输出每条选中的边及其权重。例如：
Edge Weight 0 - 1 2 1 - 2 3 0 - 3 6 1 - 4 5
总权重为 2+3+6+5=16，构成一棵最小生成树。
时间复杂度为 O(V²)，适合稠密图。若用优先队列优化可降至 O(E log V)，但邻接矩阵下不易实现稀疏结构。
基本上就这些。掌握这个版本有助于理解Prim核心机制，后续可拓展为邻接表或动态图处理。
