在 C++ 中,实现最小生成树(MST)的常用算法有两种:Prim 算法Kruskal 算法。这两种算法适用于加权无向图,用于寻找包含所有顶点的边的集合,使得边的总权重最小,且没有环路。

1. Prim 算法

Prim 算法通过贪心策略来构建 MST,从任意起始顶点开始,每次选择权重最小的边扩展 MST。

实现步骤

  1. 初始化一个集合 MST,包含图中的任意一个顶点。
  2. 找到从集合 MST 到剩余顶点中权重最小的边,并将该边加入 MST
  3. 重复步骤 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) {}
};

// 使用 Prim 算法计算最小生成树的总权重
int primMST(const vector<vector<Edge>>& graph, int start) {
int n = graph.size(); // 顶点数
vector<bool> inMST(n, false); // 标记顶点是否在 MST 中
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 最小堆

int totalWeight = 0;
pq.push({0, start}); // 起始顶点的权重为0

while (!pq.empty()) {
auto [weight, u] = pq.top(); // 获取权重最小的边
pq.pop();

if (inMST[u]) continue; // 如果已经在 MST 中,跳过

inMST[u] = true; // 标记顶点 u 在 MST 中
totalWeight += weight; // 累加边的权重

// 遍历 u 的所有邻接边
for (const auto& edge : graph[u]) {
int v = edge.to;
int w = edge.weight;

if (!inMST[v]) {
pq.push({w, v}); // 将未加入 MST 的顶点及其权重放入优先队列
}
}
}

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));

// 从顶点 0 开始计算最小生成树的总权重
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 中,前提是不会形成环。

实现步骤

  1. 将图中的所有边按权重从小到大排序。
  2. 初始化一个并查集,用于判断是否会形成环。
  3. 依次选择权重最小的边,如果该边连接的两个顶点属于不同的集合,则将其加入 MST。
  4. 重复步骤 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; // u 和 v 在同一个集合中

// 联合集合,按秩合并
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;
}
};

// 使用 Kruskal 算法计算最小生成树的总权重
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; // 当使用的边数达到 n-1 时,停止
}
}

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 算法适用于稀疏图(边少),通过边排序和并查集来实现。

这两种算法都能高效地找到图的最小生成树,但适用的场景略有不同。