2 - 最小生成树

发表于 2024-05-05 分类于 cpp ，数据结构与算法， 3-搜索与图论，图论阅读次数： Waline：本文字数： 4.8k 阅读时长 ≈ 4 分钟

快速入门图论！本文介绍最小生成树是什么，以及获得最小生成树的Kruskal算法、Prim算法。

最小生成树

首先了解一下什么是图的“生成树”。就是在图中找一棵包含图中所有节点的树，也就是含有图中所有顶点的“无环连通子图”。

因此一个图可能有多种生成树，如果图是带权的，那么 最小生成树就是权重和最小的生成树。

Prim算法

思路

抽象出两个集合，集合S和集合Other：

集合S保存已经加入到最小生成树的节点。
集合Other保存未加入到最小生成树的节点，刚开始所有节点都在Other中。

需要维护两个数组：

dist数组，表示集合Other中的节点距离整个集合S的最短距离。
visited数组，表示所有节点的访问情况，即该点是否被加入到集合S中。

算法的具体步骤如下：

在集合Other中，找到离集合S距离最近的点t。
用点t更新dist数组（其他点到集合S的距离），因为它将被加入集合S。
将点t加入集合S中。

代码实现

vector<int> dist(n, 0x3f), visited(n, 0);
void prim()
{
    int sum = 0;
    // Prim, 这里用1起点的邻接矩阵存储图了
    for (int i = 0; i < n; ++i)
    {
        // 1.找到离集合S最近的点t
        int t = -1;
        for (int j = 1; j <= n; ++j)
        {
            if (!visited[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        // 找不到t, 说明是非连通图
        if (i && dist[t] == 0x3f)
        	return;
        // 更新最小生成树权值和
        if (i)	sum += dist[t];
        // 2.更新dist
        for (int j = 1; j <= n; ++j)
            dist[j] = min(dist[j], g[t][j]);
        // 3.把点t加入集合S
        visited[t] = 1;
    }
    
    cout << sum << endl;
}

Kruskal算法

思路

Kruskal算法是并查集算法在图上的实际应用，并查集主要用来保证最小生成树的合法性（没有环）。如何用并查集去保证当前图是一棵树，详见 261. 以图判树 - 力扣（LeetCode），题解在下面。

要想保证当前图是最小生成树，需要图的所有边满足：

包含图中的所有节点；
形成的图是树结构（没有环&&只有一个集合）；
边权重和最小。

前两点用并查集很容易满足，而第三点实际上是个 贪心问题。我们只需将所有边按照权重从小到大排序，然后用并查集建生成树就行了。Kruskal算法的思路如下：

将所有边按照权重从小到大排序；
从权重最小的边开始遍历，如果：
1. 加入这条边后不会生成环，就加入这条边；
2. 加入这条边后会生成环，就不加入这条边；
得到最小生成树。

该算法时间主要花在排序上了，时间复杂度为，其中N为边的数量，因此，推荐稀疏图（边少）使用Kruskal算法。

代码实现

struct Edge
{
    int a, b, val;
    
    bool operator< (const Edge& rhs) const {
        return val < rhs.val;
    }
};

void kruskal(vector<Edge>& edges)
{
    UF uf(n);
    
    // 1.排序边
    sort(edges.begin(), edges.end());
    // 2. 遍历边, 生成最小生成树
    int res = 0, edgeCnt = 0;
    for (auto& edge : edges)
    {
        int a = edge.a, b = edge.b, val = edge.val;
        if (!uf.isConnect(a, b))
        {
            uf.connect(a, b);
            res += val;
            edgeCnt++;
        }
    }
    
    // 判断是否合法
    // ...
}

练习题

并查集判树

261. 以图判树 - 力扣（LeetCode）

可以发现，对于添加的这条边，如果该边的两个节点本来就在同一集合里，那么添加边后会产生环；如果该边的两个节点不在同一集合里，那么添加边后不会产生环。我们在添加边的过程中需要注意这个规律。

此外，在添加边结束后，还要保证集合数量只有1个，只有这样才是图的生成树。

参考代码如下：

struct UF
{
    vector<int> pa;
    int count;

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

    void connect(int a, int b)
    {
        pa[find(a)] = find(b);
        count--;
    }

    bool isConnected(int a, int b)
    {
        return find(a) == find(b);
    }

    UF(int n) : pa(n + 5), count(n)
    {
        iota(pa.begin(), pa.end(), 0);
    }
};

bool validTree(int n, vector<vector<int>>& edges) {
    UF uf(n);
    // 遍历边集数组
    for (auto& edge : edges)
    {
        int a = edge[0], b = edge[1];
        // 如果两节点在一个集合里, 再添加边会产生环
        if (uf.isConnected(a, b))
            return false;
        // 否则就是边
        else
            uf.connect(a, b);
    }
    return uf.count == 1;
}

最小生成树

1135. 最低成本连通所有城市 - 力扣（LeetCode）

Kurskal

struct UF {
    vector<int> pa;
    int count;

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

    void add(int a, int b) {
        pa[find(a)] = find(b);
        count--;
    }

    bool isConnect(int a, int b) { return find(a) == find(b); }

    UF(int n) : pa(n + 5), count(n) { iota(pa.begin(), pa.end(), 0); }
};

int minimumCost(int n, vector<vector<int>>& connections) {
    UF uf(n);

    // Kurskal
    sort(connections.begin(), connections.end(), [](const auto& v1, const auto& v2)
         {
             return v1[2] < v2[2];
         });

    int ans = 0;
    for (const auto& edge : connections)
    {
        int a = edge[0], b = edge[1], val = edge[2];
        if (!uf.isConnect(a, b))
        {
            uf.add(a, b);
            ans += val;
        }
    }

    if (uf.count == 1)
        return ans;
    else
        return -1;
}

1584. 连接所有点的最小费用 - 力扣（LeetCode）

Prim

这道题给了所有点，需要先建边，造的图必然是稠密的，因此更适合用Prim算法求最小生成树。

int minCostConnectPoints(vector<vector<int>>& points) {
    // 先建边
    int n = points.size();
    int maxVal = numeric_limits<int>::max();
    vector<vector<int>> graph (n, vector<int>(n, maxVal));
    for (int i = 0; i < points.size(); ++i) {
        for (int j = 0; j < points.size(); ++j) {
            int xi = points[i][0], yi = points[i][1];
            int xj = points[j][0], yj = points[j][1];
            int val = abs(xi - xj) + abs(yi - yj);
            graph[i][j] = graph[j][i] = min(maxVal, val);
        }
    }

    // 然后Prim
    vector<int> dist(n, maxVal), vis(n, 0);
    int ans = 0;
    for (int i = 0; i < n; ++i)
    {
        int t = -1;
        for (int j = 0; j < n; ++j)
            if (!vis[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        if (i)
            ans += dist[t];

        for (int j = 0; j < n; ++j)
            dist[j] = min(dist[j], graph[t][j]);

        vis[t] = 1;
    }

    return ans;
}

Kruskal

这道题给了所有点，所以先建边。

struct UF {
    vector<int> pa;
    int count;

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

    void add(int a, int b) {
        pa[find(a)] = find(b);
        count--;
    }

    bool isConnect(int a, int b) { return find(a) == find(b); }

    UF(int n) : pa(n + 5), count(n) { iota(pa.begin(), pa.end(), 0); }
};

struct Edge
{
    int a, b, v;

    bool operator< (const Edge& rhs) const 
    {
        return v < rhs.v;
    }

    Edge(int a, int b, int v) : a(a), b(b), v(v) {}
};

int minCostConnectPoints(vector<vector<int>>& points) {
    // 先建边
    vector<Edge> edges;
    for (int i = 0; i < points.size(); ++i)
    {
        for (int j = 0; j < points.size(); ++j)
        {
            if (i != j)
            {
                int xi = points[i][0], yi = points[i][1];
                int xj = points[j][0], yj = points[j][1];
                int val = abs(xi - xj) + abs(yi - yj);
                edges.emplace_back(i, j, val);
            }
        }
    }

    // 然后Kruskal
    UF uf(edges.size());

    sort(edges.begin(), edges.end());
    int ans = 0;
    for (const auto& edge : edges)
    {
        int a = edge.a, b = edge.b, val = edge.v;
        if (!uf.isConnect(a, b))
        {
            uf.add(a, b);
            ans += val;
        }
    }

    return ans;
}