Kruskal和并查集-最小生成树
并查集
vector<int> parent;（节点的根）
vector<int> rank;（按秩排序）
//初始化parent和rank数组
void Dset(int _n){
parent.resize(_n);
rank.resize(_n, 1);
for(int i = 0; i < _n; i++){
parent[i] = i;
}
};
//寻找当前节点的根
int find(int a){
return parent[a] == a ? a : find(parent[a]);
}
// 合并两个节点
bool merge(int x, int y){
int fx = find(x), fy = find(y);
if(fx==fy){
return false;
}
if(rank[fx] < rank[fy]){
swap(fx ,fy);
}
rank[fx] += rank[fy];
parent[fy] = parent[fx];
return true;
}
边
struct Edge{
int len, start, end;
Edge(int len, int start, int end) : len(len), start(start), end(end){};
};
Main函数
int minCostConnectPoints(vector<vector<int>>& points) {
auto dis = [&](int x, int y) -> int{
return abs(points[x][0] - points[y][0]) + abs(points[x][1] - points[y][1]);
};
vector<Edge> edge;
int n = points.size();
Dset(n);
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
edge.emplace_back(dis(i, j), i, j);
}
}
sort(edge.begin(), edge.end(), [](Edge a, Edge b) -> bool{ return a.len < b.len;});
int res = 0;
int num = 0;
for(auto & [len, i, j] : edge){
if(merge(i, j)){
res += len;
num++;
if(num==n-1)
break;
}
}
return res;
}
流程介绍
- 计算节点之间的距离：匿名函数lamda，//points[x]表示第一个节点，points[y]表示第二个节点, 不要搞混
- 初始化并查集
- 初始化边edge
- 边按从小到大排序
- 遍历边的每一对节点，每次merge两个节点，res加上边的权值，合并一次节点num++，直到num==n-1，表示边的数量已经是最小生成树了
tips
- 匿名函数 auto dis = [&](int a) ->{ return a; };
这里的[&]，表示Lambda表达式中的一种捕获方式，&表示按引用捕获函数参数，好处是不需要拷贝points数组，减少内存开销；
2. 有参构造：成员初始化列表的语法是在构造函数参数列表之后加上冒号，之后是一系列成员变量和它们对应的初值，使用逗号分隔。
struct Edge{
int len, start, end;
Edge(int len, int start, int end) : len(len), start(start), end(end){};
};
3.有趣的点，在merge函数中，parent[fy] = fx;和parent[fy] = parent[fx];是等价的，这是因为在 parent 数组中存储的值实际上并不是每个点的父节点，而是每个点所属的连通分量的代表元素（即根节点）。因此，parent[fy] = parent[fx] 的作用实际上是将 fy 所属的连通分量的根节点更新为 fx 所属的连通分量的根节点，从而将两个连通分量合并成一个。
投递淘天集团等公司10个岗位 >
