c++用kruskal算法求邻接矩阵的最小生成树的最小权值和

Kruskal算法是一种用于寻找无向图中最小生成树（Minimum Spanning Tree, MST）的经典贪心算法。在C++中，我们可以按照以下步骤使用该算法：

1. **排序边**：首先对所有边按权重从小到大排序。

2. **初始化**：创建一个空的集合表示已选择的边，以及一个空的最小生成树。

3. **遍历边**：对于排序后的每条边，检查它是否将当前的连通分量连接在一起。如果不会形成环（即这条边连接的是两个不同的连通分量），则加入最小生成树并更新已选择边的集合。

4. **结束条件**：当添加了n-1条边时（n为节点数），我们就得到了最小生成树。因为最小生成树恰好包含n-1条边，可以完全连接所有的节点。

5. **计算最小权值和**：最后，最小生成树的所有边权值之和即为所求的最小权值和。

以下是简化版的C++代码示例：

#include <vector>
#include <set>
#include <algorithm>

struct Edge {
    int src, dest, weight;
};

bool is_connected(const std::vector<Edge>& edges, int u, int v) {
    return std::find_if(edges.begin(), edges.end(),
        [u, v](const Edge& e) { return e.src == u && e.dest == v; }) != edges.end();
}

int kruskal_mst(const std::vector<Edge>& edges, int num_nodes) {
    std::sort(edges.begin(), edges.end(), [](Edge a, Edge b) { return a.weight < b.weight; });
    std::vector<int> parent(num_nodes, -1);
    std::vector<Edge> mst;

    for (Edge edge : edges) {
        int u = edge.src, v = edge.dest;
        if (parent[u] != parent[v]) {
            // 如果边连接了不同的连通分量，将其加入MST
            mst.push_back(edge);
            parent[u] = v;
        }
        if (mst.size() == num_nodes - 1)
            break;
    }

    int min_cost = 0;
    for (const Edge& e : mst)
        min_cost += e.weight;
    return min_cost;
}