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 tWeightn";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 < 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 = minKey(key, mstSet); 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];}printMST(parent, graph);
}
运行与输出说明
调用primMST(graph)后，程序输出每条选中的边及其权重。例如：
Edge Weight0 - 1 21 - 2 30 - 3 61 - 4 5
总权重为 2+3+6+5=16，构成一棵最小生成树。
时间复杂度为 O(V²)，适合稠密图。若用优先队列优化可降至 O(E log V)，但邻接矩阵下不易实现稀疏结构。
基本上就这些。掌握这个版本有助于理解Prim核心机制，后续可拓展为邻接表或动态图处理。
以上就是C++怎么实现一个最小生成树Prim算法_C++图论算法与邻接矩阵实现的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1485899.html
微信扫一扫 
支付宝扫一扫 
