破圈法实现最小生成树邻接矩阵存储C++

破圈法（Kruskal's Algorithm），也称为贪心算法，是一种用于求解无向加权图中最小生成树的算法。在邻接矩阵表示的图中，它通过一次遍历边集合，每次选择当前未加入生成树的最短边，直到所有顶点都被连接起来形成一棵树。

以下是使用C++实现破圈法的步骤：

#include <vector>
#include <algorithm>

// 图的邻接矩阵表示
typedef int Weight;
struct Edge {
    int src, dest;
    Weight weight;
};

bool compareEdges(Edge a, Edge b) { // 边比较函数，按权重从小到大排序
    return a.weight < b.weight;
}

std::vector<Edge> kruskalMST(const std::vector<std::vector<Weight>>& graph, int n) {
    std::vector<Edge> edges; // 存储所有边
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            edges.push_back({i, j, graph[i][j]});

    sort(edges.begin(), edges.end(), compareEdges); // 排序

    std::vector<int> parent(n, -1); // 妥善初始化父节点数组
    std::vector<bool> visited(n, false);

    std::vector<Edge> mst; // 最小生成树
    for (const auto& edge : edges) {
        int u = edge.src, v = edge.dest;
        if (parent[u] == -1 && parent[v] == -1) { // 如果两个端点均未访问
            mst.push_back(edge);
            parent[u] = v;
            parent[v] = u;
        } else if (parent[u] != -1 && parent[u] != v) { // 如果u已经连接了v的父亲
            // 形成了环，跳过这条边
        }
    }

    return mst;
}