采用破圈法求一个带权连通图的最小生成树扩展目的：深入了解图的复杂操作、图遍历算法和最小生成树的概念以及最小生成树的构造运算。内容：编写一个程序exp10cpp采用破圈法求一个带权连通图的最小生成树并测试。破圈法是带权连通图求最小生成树的另一种方法其思路是任意取一个圈去掉圈上图中权最大的一个边反复执行这个步骤直到图中没有圈为止。

实现步骤：

1. 读入带权连通图的顶点数和边数，并建立邻接矩阵表示图。

2. 定义一个数组visited，表示某个顶点是否已经被访问过，初始化为false。

3. 任意选择一个起点，将visited数组中对应的元素设置为true，将该起点的所有边加入一个优先队列中。

4. 从优先队列中取出权值最小的边，如果该边连接的两个顶点都已经被访问过，则跳过，否则将该边加入最小生成树中，并将另一个顶点对应的visited数组中的元素设置为true，将该顶点的所有未访问过的边加入优先队列中。

5. 如果加入最小生成树的边数等于顶点数减一，则最小生成树构造完成，退出程序。否则返回步骤4，继续寻找下一条边。

6. 如果在步骤4中发现有圈，就从圈上找到权值最大的边，将其从最小生成树中删除，并继续执行步骤4。

代码实现：

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

const int MAXN = 100;

int n, m;
int g[MAXN][MAXN]; // 邻接矩阵表示图
bool 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;
}
``