生成树

Prim：从一颗小树长大

思路和 Dijkstra 基本一致，唯一不同就是 dist 记录的是与集合的距离而非与起点的距离

// Leetcode 1584 连接所有点的最小费用
// points = [[0,0],[2,2],[3,10],[5,2],[7,0]] 求坐标轴上这几个点的最小生成树的路径和
struct Node{ // 用来在优先队列里用
    int node;
    int dis;
    bool operator>(const Node& ano) const {
        return this->dis > ano.dis;
    }
};

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size(); // 节点数
        vector<vector<int>> graph(n, vector<int>(n, INT_MAX));
        for (int i = 0; i < n; ++i){ // 建图
            for (int j = 0; j < i; ++j){
                graph[i][j] = abs(points[i][0]-points[j][0]) + abs(points[i][1]-points[j][1]);
                graph[j][i] = graph[i][j];
            }
        }  
        priority_queue<Node, vector<Node>, greater<Node>> pq;
        vector<int> dist(n, INT_MAX);
        pq.push(Node({0, 0})); // 从0开始， 0到0的距离是0
        int ret = 0;
        while(!pq.empty()){
            Node cur = pq.top(); pq.pop();
            // 跟Dijkstra一样，但人家遇到终点直接可以break
            // 因为采用优先队列的方式，队列里会有重复，第一次接触的肯定是最优解，后面
            // 重复的都是大于最优解的，直接跳过，或者你用一个数组，存储对应节点最优dist
            // 每次存储比较取最小值，但是空间浪费太大了，不如这样好
            if(dist[cur.node] == 0) continue;
            dist[cur.node] = 0;
            ret += cur.dis;
            for(int i=0; i<n; ++i){
                if(dist[i] > graph[cur.node][i]){
                    dist[i] = graph[cur.node][i];
                    pq.push(Node({i, graph[cur.node][i]}));
                }
            }
        }
        return ret;
    }
};

Kruskal

利用并查集的思想

// Leetcode 1584 连接所有点的最小费用
// points = [[0,0],[2,2],[3,10],[5,2],[7,0]] 求坐标轴上这几个点的最小生成树的路径和
class UFSet{
public:
    UFSet(int _n):count(_n), parent(_n, -1){}
    int getCount(){return count;}
    void unite(int a, int b){
        int f1 = find(a);
        int f2 = find(b);
        if(f1 == f2) return;
        if(parent[f1] < parent[f2]){
            parent[f1] += parent[f2];
            parent[f2] = f1;
        }else{
            parent[f2] += parent[f1];
            parent[f1] = f2;
        }
        -- count;
    }
    bool isConnected(int a, int b){
        return find(a) == find(b);
    }
    
private:
    int find(int pos){
        if(parent[pos] < 0) return pos;
        return parent[pos] = find(parent[pos]);
    }
    int count; // 连通集的个数
    vector<int> parent;
};

struct Edge{
    int from;
    int to;
    int weight;
    bool operator>(const Edge& ano) const {
        return this->weight > ano.weight;
    }
};

class Solution {
public:
    // 都不用建图，直接把边放进去就行了
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();
        UFSet ufs(n);
        priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
        for(int i=0; i<n; ++i){
            for(int j=0; j<i; ++j){
                int weight = abs(points[i][0]-points[j][0]) + abs(points[i][1]-points[j][1]);
                pq.push(Edge({i, j, weight}));
            }
        }
        int res = 0, cnt = 0;
        while(!pq.empty() && cnt<n-1){
            Edge cur = pq.top(); pq.pop();
            if(ufs.isConnected(cur.from, cur.to) == false){ // from和to是图节点名，这里直接以points顺序的下标来表示
                ufs.unite(cur.from, cur.to);
                res += cur.weight;
                ++cnt;
            }
        }
        return res;
    }
};