c++代码图-克鲁斯卡尔算法求最小生成树

在C++中，克鲁斯卡尔(Kruskal's Algorithm)是一种用于寻找无向加权图中最小生成树的算法。下面是基本步骤：

#include <iostream>
#include <vector>
#include <set>

using namespace std;

// 定义边的数据结构
struct Edge {
    int u, v, weight;
};

bool compareEdges(const Edge& e1, const Edge& e2) {
    return e1.weight < e2.weight;
}

// 克鲁斯卡尔算法
int kruskal(vector<Edge>& edges, int n) {
    set<int> mstSet; // 存储最小生成树的边
    sort(edges.begin(), edges.end(), compareEdges); // 按权重排序

    int result = 0; // 最小生成树的总权重

    for (int i = 0; i < edges.size(); i++) {
        Edge e = edges[i];
        if (mstSet.find(e.u) == mstSet.end() && mstSet.find(e.v) == mstSet.end()) { // 如果这条边不在已选集合中
            mstSet.insert(e.u);
            mstSet.insert(e.v);
            result += e.weight; // 添加边的权重到结果中
        }
    }

    return result; // 返回最小生成树的总权重
}

int main() {
    vector<Edge> edges = {{1, 2, 7}, {1, 5, 9}, {2, 3, 8}, {3, 4, 10},
                          {4, 5, 11}, {6, 7, 15}, {6, 8, 14}};
    int vertices = 7; // 图的顶点数
    cout << "Minimum Spanning Tree with Kruskal's algorithm: " << kruskal(edges, vertices) << endl;
    return 0;
}

在这个例子中，我们首先创建了一个`Edge`结构体来表示每条边，包括起始点、终点和权重。然后对边按权重排序，接着遍历排序后的边，每次选择不在最小生成树集（用`std::set`表示，避免添加重复边）中的最小权重边，直到所有节点连通为止。