Prim算法从点出发，每次选最近顶点加入生成树，适合稠密图；Kruskal按边权排序贪心选取，用并查集判环，适合稀疏图；两者时间复杂度分别为O(V²)和O(E log E)，应根据图的密度选择。
在图论中，最小生成树（Minimum Spanning Tree, MST）是连接无向连通图中所有顶点的一棵树，且边的权值总和最小。C++中常用的两种求解MST的算法是Prim算法和Kruskal算法。下面详细介绍它们的原理与实现方式。
Prim算法：从点出发构建最小生成树
Prim算法的核心思想是从一个起始顶点开始，逐步扩展生成树，每次选择与当前生成树相连且权值最小的边所连接的新顶点，直到覆盖所有顶点。
适用场景：稠密图（边数接近顶点数平方），使用邻接矩阵存储更高效。
Prim算法步骤：
立即学习“C++免费学习笔记（深入）”；
初始化一个布尔数组visited标记顶点是否已加入生成树，距离数组dist记录各顶点到生成树的最短距离从任意起点（如0号顶点）开始，更新其邻接点的距离每次从未访问顶点中选出dist最小的顶点u，将其加入生成树用u更新其所有邻接点的距离重复上述过程直到所有顶点都被访问
代码实现（邻接矩阵）：
#include #include #include using namespace std;const int INF = INT_MAX;
int prim(vector<vector>& graph, int n) {vector dist(n, INF);vector visited(n, false);dist[0] = 0;int totalWeight = 0;
for (int i = 0; i < n; i++) { int u = -1; for (int j = 0; j < n; j++) { if (!visited[j] && (u == -1 || dist[j] < dist[u])) u = j; } if (dist[u] == INF) return -1; // 图不连通 visited[u] = true; totalWeight += dist[u]; for (int v = 0; v < n; v++) { if (graph[u][v] != 0 && !visited[v] && graph[u][v] < dist[v]) { dist[v] = graph[u][v]; } }}return totalWeight;
}
Kruskal算法：按边排序贪心选取
Kruskal算法基于贪心策略，将所有边按权值从小到大排序，依次尝试加入生成树，若加入后不形成环，则保留该边，否则跳过。
适用场景：稀疏图（边较少），使用边列表存储效率更高。
Kruskal算法关键点：
需要对边进行排序使用并查集（Union-Find）判断是否形成环当加入n-1条边时，生成树完成
代码实现：
#include #include #include using namespace std;struct Edge {int u, v, weight;bool operator<(const Edge& other) const {return weight < other.weight;}};
class UnionFind {vector parent;public:UnionFind(int n) {parent.resize(n);for (int i = 0; i < n; i++) parent[i] = i;}
int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x];}void unite(int x, int y) { parent[find(x)] = find(y);}bool connected(int x, int y) { return find(x) == find(y);}
};
int kruskal(vector& edges, int n) {sort(edges.begin(), edges.end());UnionFind uf(n);int totalWeight = 0;int edgesAdded = 0;
for (const Edge& e : edges) { if (!uf.connected(e.u, e.v)) { uf.unite(e.u, e.v); totalWeight += e.weight; edgesAdded++; if (edgesAdded == n - 1) break; }}return edgesAdded == n - 1 ? totalWeight : -1; // 不连通返回-1
}
两种算法对比与选择建议
理解两者差异有助于在实际问题中做出合适选择。
时间复杂度比较：
Prim（邻接矩阵）：O(V²)，适合顶点少、边多的情况Prim（优先队列优化）：O(E log V)，适用于稀疏图Kruskal：O(E log E)，主要开销在排序，适合边较少的图
空间复杂度：
Prim通常使用邻接矩阵或邻接表，空间O(V²)或O(E)Kruskal只需存储边列表，空间O(E)
选择建议：
图很稠密（比如完全图）→ 优先考虑Prim图较稀疏或边已以列表形式给出 → Kruskal更直观高效需要频繁添加/删除边 → Kruskal更容易维护
基本上就这些。两种算法都能正确求出最小生成树，关键是根据数据规模和结构选择合适的方法。实际编程中注意处理图不连通的情况，避免无限循环或错误结果。
以上就是C++如何实现一个最小生成树算法_C++图论之Prim与Kruskal算法详解的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1485357.html
微信扫一扫 
支付宝扫一扫 
