Minimum Spanning Tree

2021-01-21

motivation

最近Leetcode每日一题老是遇到minimum spanning tree的问题, 刚好算法课没有讲到, 就自己学习一下.

我的定义

MST是具有n个结点和权值和最小的n-1条边的联通无环无向图(树)

主要算法

1 Kruskal

CLRS pseudocode:

解释:

贪心思想, 每次选取不成环的最小权重边
需要用到并查集
朴素实现需要用到堆
也可以不使用堆, 直接根据权值sort, 然后所有边都UNION.

应用举例: https://leetcode-cn.com/problems/min-cost-to-connect-all-points/ leetcode1584

想象每一对结点之间都有边, 共 C n 2 = n(n - 1) 条边, 选n - 1 条;

class Solution {
public:
    struct Node { // definition of edge
        int v1;
        int v2;
        int dist;
    };

    struct cmp {
        bool operator()(Node &a, Node &b) {  // 小根堆
            return a.dist > b.dist;
        }
    };

    int find(vector<int> &father, int x) { // 并查集核心代码
        if (x != father[x]) father[x] = find(father, father[x]);
        return father[x];
    }
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();
        vector<int> father(n);
        for (int i = 0; i < n; ++i) {
            father[i] = i;  // 对应pseudocode line2, 3
        }
        priority_queue<Node, vector<Node>, cmp> pq;  // 小根堆
        // in pq all edges
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                Node node;
                node.v1 = i;
                node.v2 = j;
                node.dist = abs(points[i][1] - points[j][1]) + abs(points[i][0] - points[j][0]);
                pq.push(node);
            }
        }
        int res = 0, cnt = 0;
        while (cnt < n - 1) { // 算法导论代码会TLE, 改成选出n - 1条边的时候停止
            Node a = pq.top();
            pq.pop();
            int f1 = find(father, a.v1), f2 = find(father, a.v2);
            if (f1 != f2) {  // 不会成环
                res += a.dist;
                father[f1] = f2;
                cnt++;
            }
        }
        return res;
    }
};

2 Prim

CLRS pseudocode:

同样对上一道leetcode运用prim解法:

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();
        int res = 0;
        int graph[1005][1005], dist[1005], vis[1005] = {0};
        memset(dist, 0x3f, sizeof dist); // 初始化, 所有距离为INF
        // 建图
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                graph[i][j] = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);  // 无向图, i j , j i做了重复计算
            }
        }
        // prim
        // 类似于dijkstra
        for (int i = 0; i < n; ++i) { // 选完n个点, MST已经构造完成
            int t = -1;
            for (int j = 0; j < n; ++j) {
                if (!vis[j] && (t == -1 || dist[t] > dist[j])) { // 选出最近的点
                    t = j;
                }
            }
            if (i) res += dist[t];  // 第一个点无需统计距离, 一开始全部是inf
            vis[t] = 1;
            // relax
            for (int j = 0; j < n; ++j) {
                if (!vis[j]) dist[j] = min(dist[j], graph[t][j]);
            }
        }
        return res;
    }
};

Leetcode 1489 hard 找到最小生成树里的关键边和伪关键边

1489. 找到最小生成树里的关键边和伪关键边 - 力扣（LeetCode） (leetcode-cn.com)

如果从图中删去某条边，会导致最小生成树的权值和增加，那么我们就说它是一条关键边。伪关键边则是可能会出现在某些最小生成树中但不会出现在所有最小生成树中的边。

弄清定义:

关键边: 出现在所有MST中, 所以如果一开始我们就把这条边删掉(全程不用这条边), 那么要么生不成MST, 要么生成的MST总代价变大
伪关键边: 这条边属于某一个MST, 但不被所有MST共有, 为了确保这条边一定被选中, 我们应该一开始就union这条边.

算法步骤:

先计算无任何修改情况下MST的代价cost, 作为后续判断的依据
枚举每一条边:
- 判断是不是critical, 如果是, continue
- 判断是不是pseudo critical

class UF {
public:
    vector<int> p; // parent
    int setCount;  // 集合个数, 如果能生成MST, 其最终值应该为1
    // ctor
    UF(int n) : setCount(n){
        p.resize(n);
        for (int i = 0; i < n; ++i) {
            p[i] = i;
        }
    }

    int find(int x) {
        if (x != p[x]) p[x] = find(p[x]);
        return p[x];
    }

    bool connect(int a, int b) {
        int x = find(a), y = find(b);
        if (x != y) {
            p[x] = y;
            --setCount;
            return true;
        }
        return false;
    }
};

class Solution {
public:
    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
        // 因为题目要返回下标
        int m = edges.size();
        for (int i = 0; i < m; ++i) {
            edges[i].push_back(i); // 给边编号
        }
        sort(edges.begin(), edges.end(), [&](auto &a, auto &b) {
            return a[2] < b[2];  // 根据权值排序
        });
        // 计算正常无修改的MST权值
        UF uf(n);
        int cost = 0;
        for (int i = 0; i < m; ++i) {
            if (uf.connect(edges[i][0], edges[i][1])) {
                cost += edges[i][2];
            }
        }

        vector<vector<int>> res(2); // res[0] 为关键边, res[1]为伪关键边
        for (int i = 0; i < m; ++i) { // 关键边, 伪关键边放在一起做
            // critical, 不使用该边, 所以初始value为0
            UF uf(n);
            int value = 0;
            for (int j = 0; j < m; ++j) {
                if (i != j && uf.connect(edges[j][0], edges[j][1])) {
                    value += edges[j][2];
                }
            }
            if (uf.setCount != 1 || value > cost) { // 关键边, 没了你就生不成MST或者代价增大
                res[0].push_back(edges[i][3]);
                continue;
            } 

            // pseudo critical
            uf = UF(n);
            value = edges[i][2]; // 使用该边
            uf.connect(edges[i][0], edges[i][1]);
            for (int j = 0; j < m; ++j) {
                if (i != j && uf.connect(edges[j][0], edges[j][1])) {
                    value += edges[j][2];
                }
            }
            if (uf.setCount== 1 && value == cost) {
                res[1].push_back(edges[i][3]); // 伪关键边
            }
        }
        return res;
    }
};