数据结构与算法 - 最小生成树

发表于 更新于 分类于

我们定义无向连通图的 最小生成树（Minimum Spanning Tree，MST）为边权和最小的生成树。

注意：只有连通图才有生成树，而对于非连通图，只存在生成森林。

1584. 连接所有点的最小费用

题目链接：https://leetcode-cn.com/problems/min-cost-to-connect-all-points/

给你一个 points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。

连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。

请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。

示例：

输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
输出：20

Kruskal 算法

Kruskal 算法是一种常见并且好写的最小生成树算法，由 Kruskal 发明。该算法的基本思想是从小到大加入边，是个贪心算法。

前置知识：

  1. 并查集：数据结构与算法 - 并查集)
  2. 贪心
  3. 图的存储（直接存边，邻接矩阵，邻接表）

代码实现：

// 这里是基础的并查集实现
class UnionFind {
private:
    vector<int> parent;
    int count;
public:
    UnionFind(int n) : count(n) {
        parent.resize(n);
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int Count() { return count;}
    int Find(int n) { return n == parent[n] ? n : parent[n] = Find(parent[n]); }
    void Union(int a, int b) {
        int rootA = Find(a), rootB = Find(b);
        if (rootA != rootB) count--, parent[rootA] = rootB;
    }
};

// 这个结构体使用直接存边的方式存图
struct Edge {
    int len, x, y;
    Edge(int len = 0, int x = 0, int y = 0) : len(len), x(x), y(y) {};
};

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        auto caldist = [&](int i, int j) -> int {
            return abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
        };
        // 1. 建图 存储方式：直接存边
        int N = points.size();
        UnionFind uf(N);
        vector<Edge> edges;
        for (int i = 0; i < N; i++) for (int j = i + 1; j < N; j++) {
            edges.emplace_back(caldist(i, j), i, j);
        }
        // 2. 排序所有的边，贪心选择较短的边
        int cost = 0;
        sort(edges.begin(), edges.end(), [](Edge &a, Edge &b) { return a.len < b.len; });
        for (auto & edge : edges) {
            // 如果这条边的左右顶点已经连接上 则跳过这条边 否则这条边加入最小生成树
            if (uf.Find(edge.x) == uf.Find(edge.y)) continue;
            uf.Union(edge.x, edge.y);
            cost += edge.len;
            if (uf.Count() == 1) return cost; // 最小生成树已经生成
        }
        return 0;
    }
};

运行结果：

Accepted
72/72 cases passed (532 ms)
Your runtime beats 58.35 % of cpp submissions
Your memory usage beats 25.13 % of cpp submissions (56.9 MB)

Prim 算法

Prim 算法是一种常见并且好写的最小生成树算法。该算法的基本思想是从一个结点开始，不断加点（而不是 Kruskal 算法的加边）。

在稠密图尤其是完全图上，暴力 Prim 的复杂度比 Kruskal 优，但不一定实际跑得更快。

代码实现：

// Distance 用来存储定点到最小生成树的距离
struct Distance {
    int index /* 定点在 points 中的索引值 */, len /* 定点到最小生成树的距离 */;
    Distance(int index = 0, int len = 0) : index(index), len(len) {};
    bool operator <(const Distance& a) const { return len > a.len; }
};

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        auto caldist = [&](int i, int j) -> int {
            return abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
        };

        int N = points.size();
        vector<int> visited(N, 0);
        int cost = 0;
        priority_queue<Distance> Q; // 优先队列 用来查找距离最小生成树最近的点
        Q.push(Distance{0, 0});
        while (!Q.empty()) {
            Distance e = Q.top();
            Q.pop();
            if (!visited[e.index]) {
                cost += e.len;
                visited[e.index] = 1; // 将找到的最近的点加入最小生成树
                for (int i = 0; i < N; i++) {
                    // 遍历计算未加入点距离最小生成树的距离 这里不是最小距离 最小距离由优先队列选择
                    if (!visited[i] && i != e.index) Q.push(Distance{i, caldist(i, e.index)});
                }
            }
        }
        return cost;
    }
};

运行结果：

Accepted
72/72 cases passed (668 ms)
Your runtime beats 24.34 % of cpp submissions
Your memory usage beats 64.91 % of cpp submissions (41.3 MB)

特殊的 Prim 算法

对于稠密图来说，有一种特殊的 Prim 算法可以达到 O(n^2) 的时间复杂度

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        auto caldist = [&](int i, int j) -> int {
            return abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
        };
        // 1. 建图 存储方式：邻接矩阵
        int N = points.size();
        vector<vector<int>> edges(N, vector<int>(N, 0));
        for (int i = 0; i < N; i++) for (int j = i + 1; j < N; j++)
            edges[i][j] = edges[j][i] = caldist(i, j);

        vector<int> distance(N, INT_MAX), visited(N, 0);
        distance[0] = 0; // 将 0 点加入最小生成树
        for (int i = 0; i < N; i++) {
            int next = -1;
            for (int j = 0; j < N; j++) { // 在剩余定点中，找到最小路径值的定点
                if (!visited[j] && (next == -1 || distance[j] < distance[next])) next = j;
            }
            visited[next] = true;         // 将找到最小路径值的定点加入最小生成树
            for (int k = 0; k < N; k++) { // 加入新定点后，导致连通分量到其他定点距离变化
                if (!visited[k]) distance[k] = min(distance[k], edges[next][k]);
            }
        }
        return accumulate(distance.begin(), distance.end(), 0);
    }
};

运行结果：

Accepted
72/72 cases passed (128 ms)
Your runtime beats 82.67 % of cpp submissions
Your memory usage beats 75.12 % of cpp submissions (26.1 MB)

参考资料