克鲁斯卡尔(Kruskal)算法求解最小生成树

克鲁斯卡尔算法是一种用于求解最小生成树的贪心算法。最小生成树是一个无向连通图中生成树（即包含图中所有顶点，并且是一棵树）中，边的权值之和最小的树。下面对克鲁斯卡尔算法的思路进行详细讲解：

1. 初始化： 将图中的所有边都去掉，形成一个空图。同时，创建一个数组（通常称为父节点数组），用于记录每个顶点所属的集合。

2. 边的排序： 将图中所有的边按照权值从小到大的顺序进行排序。

3. 逐步添加边： 按照排好序的顺序，逐个将边加入图中。在添加边的过程中，需要保证添加的边不会形成环。为了判断是否会形成环，可以利用并查集的思想。

4. 并查集的应用： 使用并查集来维护顶点所属的集合。每个顶点最初都是一个独立的集合，随着边的添加，不断合并集合。在并查集中，通过一个根节点来表示一个集合。当两个顶点所属的集合不同时，说明加入这条边不会形成环，可以将这两个集合合并。反之，如果两个顶点所属的集合相同，说明加入这条边会形成环，应该舍弃这条边。

5. 重复步骤3： 重复上一步的操作，直到连接所有顶点。此时，最小生成树就生成了。

下面是对C++实现中的关键部分的详细解释：

• Edge 结构体： 用于表示图中的边，包括起始顶点、终止顶点和权值。

• compareEdges 函数： 用于在排序时定义边的比较规则，按照权值从小到大排序。

• KruskalAlgorithm 类： 包含图的顶点数、边的集合等信息，以及执行克鲁斯卡尔算法的方法。

• addEdge 方法： 用于向图中添加边。

• runKruskal 方法： 包含克鲁斯卡尔算法的核心逻辑，按照排序后的边逐个添加，使用并查集来判断是否形成环。

• findRoot 方法： 用于找到一个顶点所属集合的根节点，采用路径压缩的方式优化查找。

• main 函数： 在主函数中创建 KruskalAlgorithm 对象，添加边，然后执行克鲁斯卡尔算法并输出最小生成树的边。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int start, end, weight;
};

bool compareEdges(const Edge& edge1, const Edge& edge2) {
    return edge1.weight < edge2.weight;
}

class KruskalAlgorithm {
private:
    int numVertices;
    vector<Edge> edges;

public:
    KruskalAlgorithm(int vertices) : numVertices(vertices) {}

    void addEdge(int start, int end, int weight) {
        Edge edge = {start, end, weight};
        edges.push_back(edge);
    }

    void runKruskal() {
        sort(edges.begin(), edges.end(), compareEdges);

        vector<int> parent(numVertices);
        for (int i = 0; i < numVertices; ++i) {
            parent[i] = i;
        }

        vector<Edge> minimumSpanningTree;

        for (const Edge& edge : edges) {
            int rootStart = findRoot(parent, edge.start);
            int rootEnd = findRoot(parent, edge.end);

            if (rootStart != rootEnd) {
                minimumSpanningTree.push_back(edge);
                parent[rootStart] = rootEnd;
            }
        }

        for (const Edge& edge : minimumSpanningTree) {
            cout << "Edge: " << edge.start << " - " << edge.end << " | Weight: " << edge.weight << endl;
        }
    }

private:
    int findRoot(vector<int>& parent, int vertex) {

        while (parent[vertex] != vertex) {
            parent[vertex] = parent[parent[vertex]];  // Path compression
            vertex = parent[vertex];
        }
        return vertex;
    }
};

int main() {
    KruskalAlgorithm kruskal(4);

    kruskal.addEdge(0, 1, 2);
    kruskal.addEdge(0, 2, 3);
    kruskal.addEdge(1, 2, 1);
    kruskal.addEdge(1, 3, 4);
    kruskal.addEdge(2, 3, 5);

    kruskal.runKruskal();

    return 0;
}