一起学习交流~

图-04-最小生成树

算法 laomuji 7个月前 (03-02) 336次浏览 已收录 0个评论

最小生成树

生成树是指有图中所有顶点,且边数最少的连通子图
最小生成树是指有图中所有顶点,且边总权重最小的连通子图

题目

力扣1584题
https://leetcode-cn.com/problems/min-cost-to-connect-all-points/

prim

从一个点开始,往其它点拓展,贪心的思想
需要用到优先级队列,把短的边放在前面
思路是 每个点都只访问一次,把该点的所有路径加入优先级队列
然后再把该点连接的点的所有路径加入优先级队列
复杂度elogv, e为边个数v为点个数
速度比Kruskal慢,但实现难度低一些,不需要并查集

class Solution {
private:
    struct Edge{//存放边数据
        int u;
        int v;
        int cost;
        Edge(int _u,int _v,int _cost){
            u = _u;
            v = _v;
            cost = _cost;
        }
        struct CMP{//用于优先级队列排序
            bool operator()(const Edge&a,const Edge&b){
                return a.cost > b.cost;
            }
        };
    };

public:
    //计算连接两条边的费用
    int getCost(vector<int>& i,vector<int>& j){
        return abs(i[0] - j[0])+abs(i[1] - j[1]);
    }

    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();//点的个数
        if(n <2)return 0;//如果少于两个点,不需要连接
        priority_queue<Edge,vector<Edge>,Edge::CMP>que;//优先级队列
        vector<bool>visit(n,false);//记录是否已经加入节点
        int start = 0;//随机选取一个起始节点 选择0 也可是其它,不影响
        visit[start] = true;//表示已访问
        int size = 1;//已经访问的点的个数
        //将与起始节点相连的节点加入队列
        //由于这个题每个点都可以相连,所以把所有路径都加入
        for(int i =0;i<n;i++){
            if(visit[i]==false)que.push(Edge(start,i,getCost(points[start],points[i])));
        }
        int result = 0;//总费用
        while(que.size()){
            if(size >= n)break;//如果所有点都访问过了跳出循环
            Edge cur = que.top();que.pop();
            //起点一定是访问过的,因为只有访问过才加入队列
            //所以不需要考虑起点了
            if(visit[cur.v]==false){//如果终点还没有访问过
                visit[cur.v]=true;//防止重复访问
                size++;//个数+1
                result+=cur.cost;
                //将所有与终点相连的边加入队列
                for(int i =0;i<n;i++){
                    if(visit[i]==false)que.push(Edge(cur.v,i,getCost(points[cur.v],points[i])));
                }
            }
        }
        return result;
    }
};

Kruskal

需要用到并查集的知识,并查集我也编写了一篇文章,可以先去看看
原理就是 每次取最小的边,判断是否属于同一个集合
如果这条边 不属于同一个集合,那么可以相连
如果这条边 属于同一个集合,那么连接会造成回路,不能相连
属于贪心的思想,由于每个点相连都是最短,所以整个生成树也最小
复杂度eloge ,e为边个数
如果 知道边的个数,可以使用数组+sort,速度会比小根堆快很多

class Solution {
private:
    class UnionFind{//基于路径压缩的并查集
        vector<int>root;
    public:
        UnionFind(int n){
            root.resize(n);
            for(int i =0;i<n;i++){
                root[i]=i;
            }
        }
        int find(int x){
            if(x == root[x])return x;
            root[x] = find(root[x]);
            return root[x];
        }
        void unionXY(int x,int y){
            int rootX = find(x);
            int rootY = find(y);
            if(rootX != rootY){
                root[rootX]=rootY;
            }
        }
        bool isConnect(int x,int y){
            return find(x) == find(y);
        }
    };

    struct Edge{//存放边数据
        int u;
        int v;
        int cost;
        Edge(int _u,int _v,int _cost){
            u = _u;
            v = _v;
            cost = _cost;
        }
        struct CMP{//用于优先级队列排序
            bool operator()(const Edge&a,const Edge&b){
                return a.cost > b.cost;
            }
        };
    };

public:
    //计算连接两条边的费用
    int getCost(vector<int>& i,vector<int>& j){
        return abs(i[0] - j[0])+abs(i[1] - j[1]);
    }
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();//点的个数
        if(n <2)return 0;//如果少于两个点,不需要连接
        priority_queue<Edge,vector<Edge>,Edge::CMP>que;//优先级队列
        for(int i =0;i<n;i++){
            //j+1 避免重复,因为i已经连接j了
            for(int j =i+1;j<n;j++){
                vector<int>&u = points[i];
                vector<int>&v = points[j];
                que.push(Edge(i,j,getCost(u,v)));
            }
        }
        UnionFind uf(n);//并查集
        int result = 0;
        //有n个点 需要n-1条边
        int size = 0;//边数
        while(que.size()){
            Edge cur = que.top();que.pop();
            if(uf.isConnect(cur.u,cur.v) == false){
                uf.unionXY(cur.u,cur.v);//连接并查集
                result +=cur.cost;
                size++;//边数+1
                if(size+1 >= n)break;//如果边数足够了,可以跳出循环了
            }
        }
        return result;
    }
};
喜欢 (3)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论