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 所属的连通分量的根节点，从而将两个连通分量合并成一个。