题解 | #最小生成树#

NC159 最小生成树

先复习下最小生成树的概念：生成树是一个图的一颗含有其所有顶点的连通子图，也就是一个树。最小生成树是所有生成树中，边的总权值最小的那个。

最小生成树有两种算法，分别是克鲁斯卡尔和prim算法，分别介绍之。

题意

给你一个无向图，n点m边，求最小生成树

1. 克鲁斯卡尔算法

克鲁斯卡尔算法的流程如下：

• 先对所有边按权值从大到小排序
• 从小到大开始遍历，如果这条边的加入：

1. 不能使现有的图成环，则加入
2. 如果能成环，舍去。

• 直到加入的边为n-1条为止。

画一个例子说明下：

• 边权排序：

• 遍历流程：

(B,C,3)未成环,加入,res=3;
(B,D,5)加入,res=8;
(A,B,6)加入,res=14;
(C,D,7)会成环,舍去;
(B,F,8)加入,res=22;
(A,E,10)加入,res=32;
已经加入了5条边,退出,返回res=32;

实现的时候，难点是如何判断环，这里用的是并查集来做，如果遍历到的边A和边B处于同一个集合，那么加入AB必会成环。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost intvector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    static const int N = 500, M = 1000;
    struct Edge {
        int from, to, next, w;
        bool operator<(const Edge &e) {
            return this->w < e.w;
        }
    } e[M];

    int head[N], idx = 1;

    void add(int u, int v, int w) {
        e[idx].from = u;
        e[idx].to = v;
        e[idx].next = head[u];
        e[idx].w = w;
        head[u] = idx++;
    }

    int f[M];

    int find(int x) {
        return (f[x] != x) ? (f[x] = find(f[x])) : f[x];
    }

    void merge(int x, int y) {
        f[find(x)] = find(y);
    }

    void initGraph(int n, int m, vector<vector<int> >& cost) {
        // 初始化前向星
        memset(head, -1, sizeof(head));
        memset(e, 0, sizeof(e));

        // 加边
        for (auto a : cost) {
            add(a[0], a[1], a[2]);
        }


        // 初始化并查集
        for (int i = 1; i <= m; i++)
            f[i] = i;
    }

    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        initGraph(n, m, cost);

        int res = 0, cnt = 0;

        // 1. 按边排序
        sort(e + 1, e + m + 1);

        // 2. 从小到大遍历
        for (int i = 1; cnt < n-1; i++) {
            int x = e[i].from, y = e[i].to;
            // 3. 不成环就加
            if (find(x) != find(y)) {
                merge(x, y);
                res += e[i].w;
                cnt ++;
            }
        }

        return res;
    }
};

• 时间复杂度: , 对边排序，并查集find函数的时间复杂度近似看做。
• 空间复杂度: . 前向星存图的空间就达到了的级别，还有一个大小为的并查集。

2. prim算法（普利姆算法）的朴素版本

prim算法的流程如下：

• 设图G=(V,E), 定义点集合S={1}, 先把1号点放进去。T为V-S的差集。
• 在所有边中找一条权值最小的边u->v，使得u在S中，v在T中，将边加入图，u点加入S。
• 迭代步骤2，n-1次。

还是以上图为例，简述prim算法的流程：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost intvector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    static const int N = 500, M = 3000;
    static const int INF = 0x3f3f3f3f;

    struct Edge {
        int from, to, next, w;
    } e[M];

    int head[N], idx = 1;
    int dis[N]; // 维护每个点到集合S的距离
    bool vis[N];

    void add(int u, int v, int w) {
        e[idx].from = u;
        e[idx].to = v;
        e[idx].next = head[u];
        e[idx].w = w;
        head[u] = idx++;
    }

    void initGraph(int n, int m, vector<vector<int> >& cost) {
        // 初始化前向星
        memset(head, -1, sizeof(head));
        memset(e, 0, sizeof(e));
        memset(dis, 0x3f, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        // 加边
        for (auto a : cost) {
            add(a[0], a[1], a[2]);
            add(a[1], a[0], a[2]); // 无向图，双向加边
        }
    }

    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        initGraph(n, m, cost);

        dis[1] = 0; // 先把1号点放进去
        int res = 0;
        for (int i = 0; i < n; i++) {
            int mst = INF, v = 0; // 当前边的最小值及终点是哪个点
            // 找所有的点，看哪个点未访问过以及到S集合最近
            for (int j = 1; j <= n; j++) {
                if (!vis[j] && dis[j] < mst) {
                    mst = dis[j];
                    v = j;
                }
            }

            // 因为肯定存在最小生成树，所以不用判断是否v仍为0
            res += mst;
            vis[v] = true; // v点加入S

            // 遍历v点的出边
            for (int j = head[v]; ~j; j = e[j].next) {
                // v->u
                int u = e[j].to;
                // 如果u不在S中，并且由于v的加入，能使得u到S的距离变短，更新之。
                if (e[j].w < dis[u] && !vis[u]) {
                    dis[u] = e[j].w;
                }
            }
        }
        return res;
    }
};

• 时间复杂度：, 对点做了两重循环
• 空间复杂度：, 依赖前向星存储。

3. 堆优化prim算法

方法2中，我们在第52-56行找V-S中距离S最近点的时候，是暴力的遍历全部点，但是如果我们按到S距离大小维护一个小根堆，每次直接取堆顶，就可以把这部分暴力逻辑优化成对数时间复杂度。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost intvector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    #define x first
    #define y second

    using pii = pair<int, int>;

    // 定义小根堆，存储当前距离1号点的距离和下标
    // 默认的priority_queue是大根堆，要特殊定义一下，这样写是固定写法。
    // stl中，pair的比较是先比第一个，再比第二个，所以距离要放前面
    using minheap = priority_queue<pii, vector<pii>, greater<pii> >;

    static const int N = 500, M = 3000;
    static const int INF = 0x3f3f3f3f;

    struct Edge {
        int from, to, next, w;
    } e[M];

    int head[N], idx = 1;
    int dis[N]; // 维护每个点到集合S的距离
    bool vis[N]; // 维护集合S

    void add(int u, int v, int w) {
        e[idx].from = u;
        e[idx].to = v;
        e[idx].next = head[u];
        e[idx].w = w;
        head[u] = idx++;
    }

    void initGraph(int n, int m, vector<vector<int> >& cost) {
        // 初始化前向星
        memset(head, -1, sizeof(head));
        memset(e, 0, sizeof(e));
        memset(dis, 0x3f, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        // 加边
        for (auto a : cost) {
            add(a[0], a[1], a[2]);
            add(a[1], a[0], a[2]); // 无向图，双向加边
        }
    }

    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        initGraph(n, m, cost);

        minheap h;

        h.push({0, 1});
        int cnt = 0, res = 0;
        while (!h.empty() && cnt < n) {
            int x = h.top().x, u = h.top().y; // x是堆顶，一定是最小距离，u是这条边指向的终点
            h.pop();

            // 如果u点在S的补集中，那么这条边就能加入最小生成树，答案+x
            if (!vis[u]) {
                res += x;
                cnt++;
                vis[u] = 1; // u加入S

                for (int i = head[u]; ~i; i = e[i].next) {
                    // u->v
                    int v = e[i].to, d = e[i].w;
                    if (d < dis[v] && !vis[v]) {
                        dis[v] = d;
                        h.push({d, v}); // v在S的补集中，插入堆
                    }                    
                }
            }            
        }

        return res;
    }
};

• 时间复杂度：, 外层是对顶点大小的堆操作，内层循环遍历边。
• 空间复杂度：, 依赖前向星存储。