在 C++ 中,实现最小生成树(MST)的常用算法有两种:Prim 算法和Kruskal 算法。这两种算法适用于加权无向图,用于寻找包含所有顶点的边的集合,使得边的总权重最小,且没有环路。
1. Prim 算法
Prim 算法通过贪心策略来构建 MST,从任意起始顶点开始,每次选择权重最小的边扩展 MST。
实现步骤
- 初始化一个集合
MST
,包含图中的任意一个顶点。
- 找到从集合
MST
到剩余顶点中权重最小的边,并将该边加入 MST
。
- 重复步骤 2,直到所有顶点都包含在
MST
中。
C++ 实现示例(使用优先队列)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
| #include <iostream> #include <vector> #include <queue> #include <climits>
using namespace std;
struct Edge { int to, weight; Edge(int t, int w) : to(t), weight(w) {} };
int primMST(const vector<vector<Edge>>& graph, int start) { int n = graph.size(); vector<bool> inMST(n, false); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int totalWeight = 0; pq.push({0, start});
while (!pq.empty()) { auto [weight, u] = pq.top(); pq.pop();
if (inMST[u]) continue;
inMST[u] = true; totalWeight += weight;
for (const auto& edge : graph[u]) { int v = edge.to; int w = edge.weight;
if (!inMST[v]) { pq.push({w, v}); } } }
return totalWeight; }
int main() { int n = 5; vector<vector<Edge>> graph(n);
graph[0].push_back(Edge(1, 2)); graph[1].push_back(Edge(0, 2));
graph[0].push_back(Edge(3, 6)); graph[3].push_back(Edge(0, 6));
graph[1].push_back(Edge(2, 3)); graph[2].push_back(Edge(1, 3));
graph[1].push_back(Edge(3, 8)); graph[3].push_back(Edge(1, 8));
graph[1].push_back(Edge(4, 5)); graph[4].push_back(Edge(1, 5));
graph[2].push_back(Edge(4, 7)); graph[4].push_back(Edge(2, 7));
int totalWeight = primMST(graph, 0); cout << "Minimum Spanning Tree Total Weight: " << totalWeight << endl;
return 0; }
|
代码解释
graph
是一个邻接表,每个顶点的邻接边存储在一个 vector
中。
priority_queue
用于选择当前权重最小的边。
inMST
数组用于标记哪些顶点已经在 MST 中。
- 算法的时间复杂度为 (O(E \log V)),其中 (E) 是边数,(V) 是顶点数。
2. Kruskal 算法
Kruskal 算法通过贪心策略来构建 MST,每次选择权重最小的边,添加到 MST 中,前提是不会形成环。
实现步骤
- 将图中的所有边按权重从小到大排序。
- 初始化一个并查集,用于判断是否会形成环。
- 依次选择权重最小的边,如果该边连接的两个顶点属于不同的集合,则将其加入 MST。
- 重复步骤 3,直到 MST 包含 (V-1) 条边。
C++ 实现示例(使用并查集)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
| #include <iostream> #include <vector> #include <algorithm>
using namespace std;
struct Edge { int from, to, weight; Edge(int f, int t, int w) : from(f), to(t), weight(w) {} };
struct UnionFind { vector<int> parent, rank;
UnionFind(int n) : parent(n), rank(n, 0) { for (int i = 0; i < n; ++i) { parent[i] = i; } }
int find(int u) { if (u != parent[u]) { parent[u] = find(parent[u]); } return parent[u]; }
bool unionSets(int u, int v) { int rootU = find(u); int rootV = find(v);
if (rootU == rootV) return false;
if (rank[rootU] > rank[rootV]) { parent[rootV] = rootU; } else if (rank[rootU] < rank[rootV]) { parent[rootU] = rootV; } else { parent[rootV] = rootU; ++rank[rootU]; } return true; } };
int kruskalMST(int n, vector<Edge>& edges) { sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) { return a.weight < b.weight; });
UnionFind uf(n); int totalWeight = 0; int edgesUsed = 0;
for (const auto& edge : edges) { if (uf.unionSets(edge.from, edge.to)) { totalWeight += edge.weight; edgesUsed++; if (edgesUsed == n - 1) break; } }
return totalWeight; }
int main() { int n = 5; vector<Edge> edges;
edges.push_back(Edge(0, 1, 2)); edges.push_back(Edge(0, 3, 6)); edges.push_back(Edge(1, 2, 3)); edges.push_back(Edge(1, 3, 8)); edges.push_back(Edge(1, 4, 5)); edges.push_back(Edge(2, 4, 7));
int totalWeight = kruskalMST(n, edges); cout << "Minimum Spanning Tree Total Weight: " << totalWeight << endl;
return 0; }
|
代码解释
- 使用
Edge
结构体来表示边,包括起点、终点和权重。
- 使用
UnionFind
类来实现并查集,用于检测是否形成环。
- 将所有边按权重排序,然后使用贪心算法构建 MST。
- 算法的时间复杂度为 (O(E \log E)),因为排序耗时 (O(E \log E)),而并查集的操作近似为 (O(\log V))。
总结
- Prim 算法适用于稠密图(边多),通常使用邻接表和优先队列实现。
- Kruskal 算法适用于稀疏图(边少),通过边排序和并查集来实现。
这两种算法都能高效地找到图的最小生成树,但适用的场景略有不同。