Kruskal 最小生成树算法 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：Kruskal 最小生成树算法

评论礼仪 见这里，违者直接拉黑。

[victory460]

// 要保证最后只形成了一棵树，即只有一个连通分量
return uf.count() == 1;

为什么一个连通分量就是一颗树啊？

[FRAOTIAC]

因为初始化的时候每个节点自己作为单独的连通分量，counts=n
而每次联通两个节点，counts--
那么最后只剩下一棵树的时候，counts==1

[C1EYE]

这俩题都要plus会员🤢

[jswxwxf]

是不是无向图找环只能用UF方案啊？感觉之前有向图的找环代码在这里不可用。

[tommyhsiao1002]

今天也思考了一下這個問題，感覺無向圖直接用visited找環的話會有點問題，因為這是有向圖，創adjacent list的時候會把from加到to也會把to加到from，
這樣會把trivial cycle也判斷成cycle 故出錯，有兩種修改方法

1. 走過node A後 把A neighbor的adjacent list中的A刪掉
2. 或是多紀錄parent node，遇到的時候直接continue就可以了
   如果有錯再麻煩指教 謝謝

[labuladong]

@jswxwxf UF 是一种方案，普通的 BFS/DFS 当然也可以，用 visited 数组辅助即可。

[ferrinweb]

@victory460 如果有大于一个连通分量，就不是一棵树了，有 n 个连通分量就有 n 棵树（如果都是树的话）

[daydayup321]

东哥那这题的话上一讲uf运用最短压缩路径的写法是不是就不能用了？因为用到了size

[jennyliulfm]

@victory460 我的理解的 多个连通分量 就成了一个森林了 每个连通分量是森林的一棵树。

[littlesquirrel2017]

c++

class UF{
public:
    int count;
    vector<int> parent;
    vector<int> size;
    UF(int n) {
        this->count = n;
        this->parent.resize(n);
        this->size.resize(n);
        for(int i=0; i<n; i++) {
            this->parent[i] = i;
            this->size[i] = 1;
        }
    }
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    void MyUnion(int p, int q) {
        int rootp = find(p);
        int rootq = find(q);
        if (rootp == rootq) return;
        if (size[rootp] > size[rootq]) {
            parent[rootq] = rootp;
            size[rootp] += size[rootq];
        }
        else {
            parent[rootp] = rootq;
            size[rootq] += size[rootp];
        }
        count--;
    }
    bool connected(int p, int q) {
        int rootp = find(p);
        int rootq = find(q);
        return rootp == rootq;
    }
    int mycount() {
        return this->count;
    }

};

struct edge {
    int _u, _v, _weight;
    edge(int u, int v, int weight):_u(u), _v(v), _weight(weight) {};
};

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();
        vector<edge> edges;
        for(int i=0; i<n; i++) {
            for(int j=i+1; j<n; j++) {
                int xi=points[i][0], yi=points[i][1];
                int xj=points[j][0], yj=points[j][1];
                edges.push_back(edge(i,j,std::abs(xi-xj)+std::abs(yi-yj)));
            }
        }
        std::sort(edges.begin(), edges.end(), [](edge a, edge b){return a._weight<b._weight;});
        int mst = 0;
        UF* uf = new UF(n);
        for(auto& edge : edges) {
            int u = edge._u;
            int v = edge._v;
            int weight = edge._weight;
            if (uf->connected(u, v)) {
                continue;
            }
            mst += weight;
            uf->MyUnion(u, v);
        }
        return mst;

    }
};

[FRAOTIAC]

C++，递归findRoot压缩

class UF {
private: 
    int count;
    vector<int> parent;

public:
    UF(int n) {
        // 一开始每个节点都是一个连通分量
        this->count = n;
        for (int i = 0;i < n; i ++) {
            parent.push_back(i);
        }
    }
    int findRoot(int x) {
        if (x != parent[x]) {
            parent[x] = findRoot(parent[x]);
        }
        return parent[x];
    }
    void connect(int p, int q) {
        int rootP = findRoot(p);
        int rootQ = findRoot(q);
        if (rootP == rootQ) {
            return;
        }

        parent[rootP] = rootQ;
        count --;
    }
    int getCount() {
        return count;
    }
    bool isConnected(int p, int q) {
        int rootP = findRoot(p);
        int rootQ = findRoot(q);
        return rootP == rootQ;
    }
 };
class Solution {
public:
    int minimumCost(int n, vector<vector<int>>& connections) {
        // 城市编号为1..n, 所以初始化大小为n+1
        UF uf(n+1);
        // 贪心的思想，就是按权重将边从小到大排序
        sort(connections.begin(), connections.end(), [&](vector<int> a, vector<int> b){return a[2] < b[2];});
        // 记录最小生成树的权重之和
        int mst = 0;

        for (auto edge: connections) {
            int u = edge[0], v = edge[1];
            int weight = edge[2];

            // 若这条边会产生环，则不能加入mst
            if(uf.isConnected(u, v)) {
                continue;
            } else {
                uf.connect(u, v);
                mst += weight;
            }
        }
        // 保证所有的节点都会联通，按理说uf.count() == 1, 说明所有的节点都联通
        // 但是因为节点0没有被使用，所以0会额外占用一个联通分量
        return uf.getCount() == 2? mst: -1;
    } 
}; 

[FebReddd]

这种题正常回溯就能解决，，对return做好处理就行。最小生成树不用也罢

[OneStarinGH]

prim快的多

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();
        vector<bool> visited(n, false);
        vector<int> min_dist(n, numeric_limits<int>::max());
        min_dist[0] = 0;
        auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) {
            return a.second > b.second;
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
        pq.push({0, 0});
        int cost = 0;
        while (!pq.empty()) {
            int u, dist;
            tie(u, dist) = pq.top();
            pq.pop();
            if (visited[u]) continue;
            visited[u] = true;
            cost += dist;
            for (int v = 0; v < n; v++) {
                if (!visited[v]) {
                    int new_dist = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1]);
                    if (new_dist < min_dist[v]) {
                        min_dist[v] = new_dist;
                        pq.push({v, new_dist});
                    }
                }
            }
        }
        return cost;
    }
};

[EyeDroplyq]

只要东哥写的，肯定看，支持东哥