贪心算法是一种在每一步选择中都采取当前状态下最优解的算法策略，旨在通过一系列局部最优选择来达到全局最优解。在图论中，最小生成树（Minimum Spanning Tree，MST）问题是一个典型的应用场景。本文将深入探讨如何利用贪心算法轻松构建最小生成树。
1. 最小生成树的概念
最小生成树是一个无向图G的子图，它包含G中的所有顶点，但只有足够的边使得这个子图成为一个树，且这些边的权重之和最小。在构建最小生成树时，我们需要遵循以下三个准则：
只能使用图中的边来构造最小生成树。
只能使用恰好n-1条边来连接图中的n个顶点（n为顶点数量）。
选用的n-1条边不能构成回路。
2. 贪心算法构建最小生成树
贪心算法构建最小生成树主要有两种方法：Kruskal算法和Prim算法。以下是这两种算法的详细介绍。
2.1 Kruskal算法
Kruskal算法的基本思想是将所有的边按边长从小到大排序，然后遍历所有边，判断每条边所连接的两个节点是否已经在树中。如果没有，则将这条边加入生成树，并合并两个节点所在的点的集合。
核心步骤：
构造一个由n个顶点组成、不含任何边的图GV，NULL，其中每个顶点自成一个连通分量。
不断从E中取出权值最小的一条边（若有多条任取其一），若该边的两个顶点来自不同的连通分量，则将此边加入到GV中。
重复步骤2，直到所有顶点在同一个连通分量上为止。
代码示例（C++）：
#include
#include
#include
using namespace std;
// 边结构体
struct Edge {
int start, end, weight;
};
// 并查集结构体
struct UnionFind {
vector
int n;
UnionFind(int n) : n(n), parent(n), rank(n, 0) {
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// 查找元素x的根节点
int find(int x) {
if (x != parent[x]) {
parent[x] = find(parent[x]);
}
return parent[x];
}
// 合并集合u和v
bool unite(int u, int v) {
int root_u = find(u), root_v = find(v);
if (root_u != root_v) {
if (rank[root_u] > rank[root_v]) {
parent[root_v] = root_u;
} else if (rank[root_u] < rank[root_v]) {
parent[root_u] = root_v;
} else {
parent[root_v] = root_u;
rank[root_u]++;
}
return true;
}
return false;
}
};
// Kruskal算法
vector
sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.weight < b.weight;
});
UnionFind uf(n);
vector
for (const Edge& edge : edges) {
if (uf.unite(edge.start, edge.end)) {
mst.push_back(edge);
}
}
return mst;
}
int main() {
// 假设图中有5个顶点，7条边
vector
{0, 1, 3}, {0, 4, 1}, {1, 2, 1}, {1, 4, 2}, {2, 3, 4},
{2, 4, 3}, {3, 4, 2}
};
int n = edges.size();
vector
for (const Edge& edge : mst) {
cout << "Edge: (" << edge.start << ", " << edge.end << ") with weight " << edge.weight << endl;
}
return 0;
}
2.2 Prim算法
Prim算法的基本思想是从一个顶点开始，逐步将其他顶点加入最小生成树中。在每一步，都选择与当前最小生成树中的顶点连接且权重最小的边。
核心步骤：
初始化：选择一个起始顶点，将其加入最小生成树中，并初始化最小生成树的边集合为空。
创建一个数组（如dist），用于存储图中所有顶点到当前最小生成树的距离（或最小边权）。初始时，除了起始顶点外，其他顶点到最小生成树的距离都设置为无穷大（或某个足够大的数）。
选择边：在所有未加入最小生成树的顶点中，选择与当前最小生成树中的顶点连接且权重最小的边。这通常通过遍历dist数组来实现，找到其中最小的非零值。
更新最小生成树：将选择的边的另一端顶点加入最小生成树中，同时将该边添加到最小生成树的边集合中。
更新dist数组：对于新加入的顶点，遍历其所有相邻顶点，如果通过新加入的顶点可以使得相邻顶点到最小生成树的距离变小，则更新dist数组中的相应值。
重复步骤3到5，直到所有顶点都加入最小生成树中。
代码示例（C++）：
#include
#include
#include
using namespace std;
// 边结构体
struct Edge {
int start, end, weight;
};
// Prim算法
vector
int n = graph.size();
vector
vector
vector
dist[start] = 0;
for (int i = 0; i < n - 1; i++) {
int u = -1;
int min_dist = INT_MAX;
for (int j = 0; j < n; j++) {
if (!visited[j] && dist[j] < min_dist) {
min_dist = dist[j];
u = j;
}
}
if (u == -1) {
break;
}
visited[u] = true;
mst.push_back({start, u, dist[u]});
for (const Edge& edge : graph[u]) {
if (!visited[edge.end] && edge.weight < dist[edge.end]) {
dist[edge.end] = edge.weight;
}
}
}
return mst;
}
int main() {
// 假设图中有5个顶点，7条边
vector
{{1, 3}, {2, 1}},
{{0, 3}, {1, 1}, {4, 2}},
{{1, 1}, {2, 4}, {4, 3}},
{{0, 1}, {3, 2}},
{{0, 2}, {3, 4}}
};
vector
for (const Edge& edge : mst) {
cout << "Edge: (" << edge.start << ", " << edge.end << ") with weight " << edge.weight << endl;
}
return 0;
}
3. 总结
本文介绍了贪心算法在构建最小生成树中的应用。Kruskal算法和Prim算法都是基于贪心策略的有效算法，可以轻松构建最小生成树。在实际应用中，我们可以根据具体问题选择合适的算法，以达到最佳效果。