cruscal算法经典题目讲解——Leetcode道路建设

道路建设 (nowcoder.com)

kruscal例题：

由题目可得，给出n个点求出n个点的最小生成树，权值计算规则为两点间的曼哈顿距离

我们采用cruscal算法实现。首先我们要先构建路线edge，我们建立一个结构体edge表示路线，包含成员变量，x，y，len分别为该路线的首位点以及路线权值。

两个循环分别计算所有路线，然后通过题目点的出现顺序对其编号，并将其存入数组中，并按照less规则排序，便于后续的路线选择（注意重载运算符

然后筛选路线，共筛选n-1个路线，每次优先取最短路线，并判断该路线的前后城市是否已被连接(通过并查集查询是否是有相同的父结点)

实现并查集——创建数组存储顶点（成员变量ufs），find函数（用来寻找父亲节点），

unionset函数（合并子树）

find函数并实现路径压缩，如果ufs[x]>=0说明父节点存放的不是最终的父结点，应当使ufs[x]赋值给其x的最终父节点的下标也就是递归使用find函数，并通过传递性将下标传给返回值。如果

unionset函数实现子树合并，则需要先判断传入的两个结点是否是一棵树上也就是通过判断其的最终根节点是否相同。如果相同直接返回false，如果不相同进行子树合并，并根据树的大小（存放的负数绝对值的大小）来决定使得规模较小得树传到规模较大的树上.实现方法为，使得规模小的树的负数加给规模大的树，然后赋值存储规模的大的结点的下标。返回true

遍历每一个边，每次边相加时，累加边的权值计算总和返回，并且计数添加的边的个数。

class Solution {
public:
    vector<int>ufs;

    int find(int x) {
        return ufs[x] >= 0 ? ufs[x] = find(ufs[x]) : x;
    }

    bool unionset(int x, int y) {
        int rootx = find(x),rooty=find(y);
        if (rootx == rooty)return false;
        if (ufs[rootx] > ufs[rooty])
            swap(rootx, rooty);
        ufs[rootx] += ufs[rooty];
        ufs[rooty] = rootx;
        return true;
    }

    struct edge {
        int len, x, y;

        edge(int len, int x, int y) 
        :len(len),x(x),y(y)
        {}

        bool operator<( const edge b) const{
            return len < b.len;
        }
    };

    int distance(vector<int>x, vector<int>y) {
        return abs(x[0] - y[0]) + abs(x[1] - y[1]);
    }

    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();
        vector<edge>edges;
        ufs.resize(n,-1);

        for (int i=0;i<n;i++)//存放边
            for (int j = i + 1; j < n;j++) {
                edges.push_back(edge(distance(points[i], points[j]), i, j));
        }

        sort(edges.begin(), edges.end(), less<edge>());//排序

        int num = 0, w = 0;
        for (size_t i = 0; i < edges.size() && num < n; i++) {
            edge tmp = edges[i];
            if (unionset(tmp.x, tmp.y)) {
                w += tmp.len;
                num++;
            }
           
        }
        return w;
    }
};