克鲁斯卡尔算法代码c++解析

克鲁斯卡尔（Kruskal's Algorithm）是一种用于求解最小生成树问题的贪心算法。它适用于边权值非负且图中无自环、无多重边的情况。以下是用C++编写的一个简单版克鲁斯卡尔算法的解析及示例代码：

#include <iostream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

// 边结构体
struct Edge {
    int u, v, w; // 起点、终点和权重
};

bool compareEdges(Edge e1, Edge e2) { // 按照权重升序比较边
    return e1.w < e2.w;
}

// 构建最小生成树
vector<Edge> kruskalMST(vector<Edge>& edges) {
    sort(edges.begin(), edges.end(), compareEdges); // 排序边按权重

    vector<Edge> mst; // 最小生成树
    set<int> parent; // 并查集，记录每个节点的根节点

    for (int i = 0; i < edges.size(); ++i) {
        Edge edge = edges[i];
        if (parent.find(edge.u) != parent.end() && parent.find(edge.v) != parent.end()) continue; // 如果两端已在一个集合中，则跳过

        // 将当前边加入最小生成树，并合并两端所在的集合
        mst.push_back(edge);
        parent.insert(edge.u);
        parent.insert(edge.v);
    }

    return mst;
}

int main() {
    vector<Edge> edges = {{0, 1, 4}, {0, 2, 8}, {1, 3, 7}, {2, 3, 9}, {1, 5, 6}, {3, 4, 5}};
    vector<Edge> result = kruskalMST(edges);

    cout << "Minimum spanning tree using Kruskal's algorithm:\n";
    for (const Edge& e : result) {
        cout << "(" << e.u << ", " << e.v << ") - Weight: " << e.w << "\n";
    }

    return 0;
}

在这个例子中，`kruskalMST`函数接收一个存储所有边的向量`edges`，首先对边进行排序，然后遍历并检查每条边是否连接着不在同一个集合（即并查集中）的顶点。如果是，就将这条边添加到最小生成树中，并将两个顶点合并到同一个集合。最后返回构建好的最小生成树。