最小生成树算法-Kruskal算法

23 Jun 2023 in Algorithm Pageviews

use kruskal easily!

最小生成树： 给定一张边带权的无向图 G=(V,E)，其中 V表示图中点的集合，E 表示图中边的集合，n=

V

，m=

E

。由 V 中的全部 n个顶点和 E 中 n−1条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G的最小生成树。

克鲁斯卡尔(Kruskal)算法

题目举例：

给定n个顶点m条边的无向图，图中可能有重边和自环，边权可能为负数，求该图最小生成树的边的权重之和。

class Solutin{
public:
    // 并查集
    int find(int x)
    {
        if (x != p[x]) {
            p[x] = find(p[x]);
        }
        return p[x];
    }

    int kruskal(vector<tuple<int, int, int>> &edges, int n)
    {
        p.resize(2 * edges.size());
        // 按照权值升序排序
        std::sort(edges.begin(), edges.end(), [](const tuple<int, int, int> &a, const tuple<int, int, int> &b){
            return std::get<2>(a) < std::get<2>(b);
        });
        std::generate(p.begin(), p.end(), [i = 0]() mutable {return i++;});

        int res = 0;
        int cnt = 0;
        for (int i = 0; i < edges.size(); i++) {
            auto [a, b, w] = edges[i];
            a = find(a);
            b = find(b);
            if (a != b) {
                p[a] = b;
                res += w;
                cnt++;
            }
        }

        return cnt < n - 1 ? INT_MIN : res;
    }

    vector<int> p;
};