Kruskal

Kruskal

Kruskal 算法是一种用于寻找加权无向图的最小生成的贪心算法

Kruskal 算法的基本思想是通过逐步选择图中权重最小的边来构建最小生成树，直到左右的顶点都被包含在树中

Kruskal 算法原理

1. 边的排序、

   首先将图中的所有的边按权重进行排序，从小到大

2. 初始化

   创建一个空的最小生成树，使用并查集（Union-Find）数据结构来管理顶点的连通性，避免形成环路

3. 选择边

   从排序后的边中，逐一检查每条边；如果当前边的两个端点属于不同的连通分量（即不在同一个集合中），则将该边加入到最小生成树中，并将这两个端点合并为一个集合中；如果当前边的两个端点属于同一个连通分量，则跳过该边，以避免形成环路

4. 重复

   重复选择边的过程，直到最小生成树中包含 V-1 条边（V 为顶点的数量）。

Kruskal 算法步骤

1. 输入图的边

   读取图的边及其权重，存储在一个边的列表中

2. 边的排序

   对边的列表进行排序

3. 初始化并查集

   为每个顶点初始化一个并查集，表示每个顶点最开始都在自己的集合中

4. 构建最小生成树

   遍历排序后的边的列表，对于每条边：使用并查集判断边的两个端点是否在同一个集合中，如果不在同一个集合，则将该边加入到最小生成树，并合并这两个集合，如果已经在同一个集合中，则跳过该边

5. 输出

时间复杂度

• 边的排序：O(E log E)。
• 并查集的操作（查找和合并）：近乎常数时间，O(α(V))，其中 α 是阿克曼函数的反函数。
• 总时间复杂度为 O(E log E)，在稀疏图中，通常 E 远小于 V²，因此 Kruskal 算法在实际应用中非常有效。

// 边的结构体
struct Edge {
    int v1, v2, weight;
};

// 并查集结构体
class UnionFind {
public:
    UnionFind(int size) {
        parent.resize(size);
        rank.resize(size, 0);
        for (int i = 0; i < size; i++) {
            parent[i] = i; // 初始化每个节点的父节点为自己
        }
    }

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

    bool unionSets(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);
        if (rootU != rootV) {
            // 按秩合并
            if (rank[rootU] > rank[rootV]) {
                parent[rootV] = rootU;
            } else if (rank[rootU] < rank[rootV]) {
                parent[rootU] = rootV;
            } else {
                parent[rootV] = rootU;
                rank[rootU]++;
            }
            return true; // 合并成功
        }
        return false; // 已经在同一集合中
    }

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

int main() {
    int V, E;
    cin >> V >> E; // 读取顶点数和边数

    vector<Edge> edges(E); // 存储所有边

    // 读取每条边
    for (int i = 0; i < E; i++) {
        cin >> edges[i].v1 >> edges[i].v2 >> edges[i].weight;
    }

    // 按边的权重排序
    sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b) {
        return a.weight < b.weight;
    });

    UnionFind uf(V + 1); // 创建并查集，节点编号从 1 到 V
    int totalWeight = 0; // 最小生成树的总权重

    // 选择边
    for (const auto &edge : edges) {
        if (uf.unionSets(edge.v1, edge.v2)) {
            totalWeight += edge.weight; // 加入到最小生成树中
        }
    }

    // 输出结果
    cout << totalWeight << endl;

    return 0;
}