力扣1584. 连接所有点的最小费用

力扣1584. 连接所有点的最小费用

题目

题目解析及思路

题目要求返回最小生成树

最小生成树模版题

法一：prim

主要思想是每次找离树最近的顶点，将其加入树种，并更新其他所有点到该点的距离

代码

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();
        int res = 0;
        int st = 0;
        vector<vector<int>> g(n,vector<int>(n));
        //建图
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                int dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
                g[i][j] = g[j][i] = dist;
            }
        }

        //存每个点到集合的最近距离
        vector<int> lowcost(n,INT_MAX);
        //已经加入集合的点不用再看
        vector<int> v(n);

        //从任意一个点开始即可，因为所有点最终都会进入集合，这里st = 0
        v[st] = 1;
        //初始化lowcost，目前只有st一个点
        for(int i=0;i<n;i++){
            if(i == st) continue;
            lowcost[i] = g[i][st];
        }

        //枚举所有店
        for(int i = 1;i<n;i++){
            //t为下一个放进集合的点的下标
            int t = -1;
            //minv为下一个放进集合的点的权值
            int minv = INT_MAX;
            //枚举所有点
            for(int j=0;j<n;j++){
                //找到lowcost最小的那个
                if(v[j] == 0 && lowcost[j] < minv){
                    t = j;
                    minv = lowcost[j];
                }
            }
            //标记，并在res中加入权值
            v[t] = 1;
            res += minv;

            //更新其他没进入集合的点到集合的距离
            for(int j=0;j<n;j++){
                if(v[j] == 0 && lowcost[j] > g[j][t]){
                    lowcost[j] = g[j][t];
                }
            }
        }
        return res;
    }
};

法二：kruskal

与prim不同，kruskal是每次找最短的边，看该边的两端是否已经联通，如果没有就连接，要用并查集

代码

class Djset{
public:
    //并查集p数组
    vector<int> parent;
    //记录树的大小
    vector<int> size;
    //存权值之和
    vector<int> len;
    int num;
    Djset(int n) : parent(n),rank(n),len(n,0),size(n,1),num(n){
        for(int i=0;i<n;i++){
            parent[i] = i;
        }
    }

    int find(int x){
        if(x != parent[x]){
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    //将x和y两点加入集合，权值为length
    int merge(int x,int y,int length){
        //找双亲
        int rootx = find(x);
        int rooty = find(y);
        //如果没连接
        if(rootx != rooty){
            parent[rooty] = rootx;
            //更新集合的大小
            size[rootx] += size[rooty];
            //更新总权值
            len[rootx] += len[rooty] + length;

            //只有当全部点加入集合才返回总权值，否则都是-1
            if(size[rootx] == num) return len[rootx];
        }
        return -1;
    }
};

struct Edge{
    int start;
    int end;
    int len;
};
class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int res = 0;
        int n = points.size();
        Djset ds(n);
        vector<Edge> edges;
        //把所有边信息加入结构体数组
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                Edge edge = {i, j, abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])};
                edges.emplace_back(edge);
            }
        }

        //根据权值排序
        sort(edges.begin(),edges.end(),[](const auto& a,const auto& b){
            return a.len < b.len;
        });

        //每次找一条边加入集合
        for(auto& e:edges){
            res = ds.merge(e.start,e.end,e.len);
            //只有当所有点都入图res才不是-1
            //才会return
            if(res != -1) return res;
        }
        return 0;
    }
};