带权连通图最小生成树：破圈法求解及代码实现

破圈法是求带权连通图最小生成树的一种方法。其思路是：任意取一个圈，去掉圈上权值最大的边，反复执行这个步骤，直到图中没有圈为止。

实现步骤：

读入图数据: 读入带权连通图的顶点数和边数，并建立邻接矩阵表示图。
初始化访问数组: 定义一个数组 visited，表示某个顶点是否已经被访问过，初始化为 false。
选择起点: 任意选择一个起点，将 visited 数组中对应的元素设置为 true，将该起点的所有边加入一个优先队列中。
从优先队列取出边: 从优先队列中取出权值最小的边。
- 如果该边连接的两个顶点都已经被访问过，则跳过。
- 否则，将该边加入最小生成树中，并将另一个顶点对应的 visited 数组中的元素设置为 true，将该顶点的所有未访问过的边加入优先队列中。
判断最小生成树是否完成: 如果加入最小生成树的边数等于顶点数减一，则最小生成树构造完成，退出程序。否则返回步骤 4，继续寻找下一条边。
处理圈: 如果在步骤 4 中发现有圈，就从圈上找到权值最大的边，将其从最小生成树中删除，并继续执行步骤 4。

代码实现：

#include <iostream>
#include <queue>
using namespace std;

const int MAXN = 100;

int n, m;
int g[MAXN][MAXN]; // 邻接矩阵表示图
boolean visited[MAXN]; // 记录哪些顶点已经被访问过
priority_queue<pair<int, pair<int, int> > > q; // 优先队列，存储边和权值

int find(int x) { // 查找根结点
    while (x != parent[x]) {
        x = parent[x];
    }
    return x;
}

void kruskal() {
    int edge_num = 0; // 记录加入最小生成树的边数
    while (!q.empty()) {
        int w = q.top().first; // 取出队头，即权值最小的边
        int u = q.top().second.first; // 取出该边连接的两个顶点
        int v = q.top().second.second;
        q.pop();
        if (visited[u] && visited[v]) { // 如果这两个顶点已经在同一个连通块中，则跳过
            continue;
        }
        visited[u] = visited[v] = true; // 标记这两个顶点已经被访问过
        cout << u << ' ' << v << ' ' << w << endl; // 输出边的信息
        edge_num++;
        if (edge_num == n - 1) { // 如果已经加入了n-1条边，则最小生成树构造完成
            break;
        }
        for (int i = 0; i < n; i++) { // 将与v相邻但未被访问过的顶点加入优先队列
            if (!visited[i] && g[v][i] != -1) {
                q.push(make_pair(g[v][i], make_pair(v, i)));
            }
        }
    }
}

int main() {
    cin >> n >> m;
    memset(g, -1, sizeof(g));
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = w;
    }
    for (int i = 0; i < n; i++) {
        parent[i] = i; // 初始化并查集
    }
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (g[i][j] != -1) { // 将每条边加入优先队列
                q.push(make_pair(g[i][j], make_pair(i, j)));
            }
        }
    }
    kruskal();
    return 0;
}

代码解析：

首先，使用 g[MAXN][MAXN] 数组存储图的邻接矩阵，visited[MAXN] 数组记录顶点是否被访问过，q 是一个优先队列，存储边的权值和边的两个顶点信息。
find(x) 函数用于查找 x 顶点的根节点，用于判断两个顶点是否在同一个连通块中。
kruskal() 函数是核心函数，它实现了破圈法求最小生成树的过程。
main() 函数负责读入图数据，并调用 kruskal() 函数求解最小生成树。

总结：

破圈法是一种简单直观的求带权连通图最小生成树的方法，它易于理解和实现。该方法的关键是不断寻找图中的圈，并删除圈上权值最大的边，直到图中没有圈为止。

注意事项：

代码中的 MAXN 需要根据图的规模进行调整。
该代码仅供参考，具体实现细节可能需要根据实际情况进行修改。

扩展：

可以尝试使用其他数据结构，例如邻接表，来表示图。
可以尝试使用其他求最小生成树的算法，例如 Prim 算法。
可以尝试将破圈法应用到其他图论问题中。