您可以自由地共享和演绎本文稿, 只需遵守开源协议[CC By 4.0]
如果这篇文章帮助到你, 可以请我喝一杯咖啡~
Kruskal算法
Kruskal算法是贪心算法的典型例子。算法连续选择开销最小的边,除非这个边的两端都已被连入树中。
这个算法的关键在于“如何判断这个边是不是有效的”,需要用到并查集。而这个并查集的合并/查找操作相当密集,因此选用静态链表并查集。
先来写个并查集:
struct UFSNode {
unsigned int classNum;
unsigned int size;
unsigned int next;
};
class UFSChain {
private:
vector<UFSNode> arr;
public:
UFSChain(int initSize = 0);
void unite(int classA, int classB);
int operator[](unsigned int index) const { return arr[index].classNum; }
};
UFSChain::UFSChain(int initSize)
: arr(initSize) {
for (int i = 0; i < arr.size(); i++) {
arr[i].classNum = i;
arr[i].size = 1;
arr[i].next = -1;
}
}
void UFSChain::unite(int classA, int classB) {
if (arr[arr[classA].classNum].size > arr[arr[classB].classNum].size) {
swap(classA, classB);
}
int str = arr[classA].classNum;
arr[arr[classB].classNum].size += arr[arr[classA].classNum].size;
while (arr[str].next != -1) {
arr[str].classNum = classB;
str = arr[str].next;
}
arr[str].classNum = arr[classB].classNum;
arr[str].next = arr[classB].next;
arr[arr[classB].classNum].next = classA;
}
主要的算法代码是非常直观的。这里将边以权重从小到大排序来模拟小堆优化。
int kruskal(const vector<vector<int>> &Graph) {
vector<vector<int>> edge;
for (int i = 0; i < Graph.size(); i++) {
for (int j = 0; j < Graph.size(); j++) {
if (Graph[i][j] != 0) {
edge.push_back({Graph[i][j], i, j});
}
}
}
sort(edge.begin(), edge.end(), [](vector<int> A, vector<int> B) {
return A[0] < B[0];
});
int res = 0;
UFSChain ufs(Graph.size());
for (int i = 0; i < edge.size(); i++) {
if (ufs[edge[i][1]] != ufs[edge[i][2]]) {
res += edge[i][0];
ufs.unite(edge[i][1], edge[i][2]);
}
}
return res;
}
适用情况
Kruskal算法需要遍历所有的边,故适用于边稀疏的情况。