最小生成树

最小生成树.pdf

最小生成树

我们可以使用 Kruskal 算法或 Prim 算法来求解图的最小生成树。这里选择使用 Kruskal 算法，它的思想是按边的权重从小到大排序，然后逐步添加边到最小生成树中，保证添加的每条边不会形成环，最终得到一个包含所有节点的生成树。

步骤：

1. 输入解析：读取节点数 N 和边数 M，接着读取每条边的节点对和权重。
2. 排序：将所有边按照权重从小到大排序。
3. 并查集：使用并查集（Union-Find）来管理图中的连通性，确保在添加一条边时不会形成环。
4. 逐步添加边：从最小的边开始，如果这条边连接的两个节点属于不同的连通块，则将其加入生成树，并合并这两个连通块。直到生成树包含 N-1 条边。

代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 并查集数据结构
class UnionFind {
public:
    UnionFind(int n) {
        parent.resize(n);
        size.resize(n, 1);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int u) {
        if (parent[u] != u) {
            parent[u] = find(parent[u]);  // 路径压缩
        }
        return parent[u];
    }

    void unionSets(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);

        if (rootU != rootV) {
            // 按秩合并，保证树的深度较小
            if (size[rootU] < size[rootV]) {
                parent[rootU] = rootV;
                size[rootV] += size[rootU];
            } else {
                parent[rootV] = rootU;
                size[rootU] += size[rootV];
            }
        }
    }

private:
    vector<int> parent;
    vector<int> size;
};

// 边的结构体
struct Edge {
    int u, v, w;
    bool operator<(const Edge& other) const {
        return w < other.w;  // 按权重升序排序
    }
};

int main() {
    int N, M;
    cin >> N >> M;
    vector<Edge> edges(M);

    // 读取边的信息
    for (int i = 0; i < M; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }

    // 对边按权重进行排序
    sort(edges.begin(), edges.end());

    // 使用并查集处理最小生成树
    UnionFind uf(N);
    int mstWeight = 0;
    int edgeCount = 0;

    for (const auto& edge : edges) {
        if (uf.find(edge.u) != uf.find(edge.v)) {
            uf.unionSets(edge.u, edge.v);
            mstWeight += edge.w;
            edgeCount++;
            if (edgeCount == N - 1) {
                break;  // 最小生成树包含 N-1 条边
            }
        }
    }

    // 输出最小生成树的权重
    cout << mstWeight << endl;

    return 0;
}

解释：

1. UnionFind 类：实现了并查集的数据结构，支持 find（查找根节点）和 unionSets（合并两个节点的连通块）。
2. Edge 结构体：每个边包含两个节点和该边的权重，并重载了 < 操作符，以便可以按权重排序。
3. 主函数：
   • 先读取所有边的输入并存储在 edges 向量中。
   • 将边按权重升序排序。
   • 使用并查集处理每条边，判断其是否可以加入到最小生成树中（即它的两个端点是否属于不同的连通块）。
   • 当已加入的边数为 N-1 时，停止算法。
   • 输出最小生成树的总权重。

复杂度：

• 时间复杂度：排序的时间复杂度为 O(M log M)，每次并查集的 find 和 union 操作平均时间复杂度为 O(α(N))（α 是反阿克曼函数，几乎是常数），因此总时间复杂度是 O(M log M + M α(N))。在最坏情况下，M ≤ 100 和 N ≤ 100，所以效率足够满足题目要求。

测试样例：

输入：

4 4
0 1 1
1 2 2
2 3 3
0 3 4

输出：

6

解释：

最小生成树包含的边是：

• 边 (0, 1) 权重 1
• 边 (1, 2) 权重 2
• 边 (2, 3) 权重 3

总权重为 1 + 2 + 3 = 6。