C语言实现带权连通图最小生成树：破圈法算法详解

#include <stdio.h> #include <stdlib.h>

#define MAX_VERTEX_NUM 20 // 最大顶点数 #define MAX_EDGE_NUM 50 // 最大边数

typedef struct { int u; // 边的起点 int v; // 边的终点 int w; // 边的权值 } Edge;

typedef struct { int n; // 顶点数 int e; // 边数 int adj[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵 } Graph;

Graph* createGraph(int n, int e); void insertEdge(Graph* G, Edge edge); void printEdges(Edge* edges, int n); void printMST(Edge* MST, int n); void breakCircle(Graph* G, Edge* edges, int* n); int find(int* parent, int i); void unionSet(int* parent, int x, int y);

int main() { int n, e; printf("请输入顶点数和边数："); scanf("%d %d", &n, &e);

Graph* G = createGraph(n, e);
Edge* edges = (Edge*)malloc(e * sizeof(Edge));  // 存储所有边
Edge* MST = (Edge*)malloc((n - 1) * sizeof(Edge));  // 存储最小生成树的边

printf("请输入每条边的起点、终点和权值：\n");
for (int i = 0; i < e; i++) {
    int u, v, w;
    scanf("%d %d %d", &u, &v, &w);
    Edge edge = {u, v, w};
    insertEdge(G, edge);
    edges[i] = edge;
}

printf("所有边按权值排序如下：\n");
printEdges(edges, e);

breakCircle(G, edges, &e);  // 破圈法求最小生成树

printf("最小生成树的边及其权值如下：\n");
printMST(MST, n - 1);

free(G);
free(edges);
free(MST);
return 0;

}

// 创建一个有n个顶点和e条边的图 Graph* createGraph(int n, int e) { Graph* G = (Graph*)malloc(sizeof(Graph)); G->n = n; G->e = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { G->adj[i][j] = 0; } } return G; }

// 向图中插入一条边 void insertEdge(Graph* G, Edge edge) { G->adj[edge.u][edge.v] = edge.w; G->adj[edge.v][edge.u] = edge.w; G->e++; }

// 输出所有边 void printEdges(Edge* edges, int n) { for (int i = 0; i < n; i++) { printf("(%d, %d) %d\n", edges[i].u, edges[i].v, edges[i].w); } }

// 输出最小生成树的边及其权值 void printMST(Edge* MST, int n) { for (int i = 0; i < n; i++) { printf("(%d, %d) %d\n", MST[i].u, MST[i].v, MST[i].w); } }

// 破圈法求最小生成树 void breakCircle(Graph* G, Edge* edges, int* n) { int parent[MAX_VERTEX_NUM]; // 并查集的父节点数组 for (int i = 0; i < G->n; i++) { parent[i] = i; }

int count = 0;  // 最小生成树的边数
for (int i = 0; i < *n; i++) {
    Edge edge = edges[i];
    int x = find(parent, edge.u);
    int y = find(parent, edge.v);
    if (x != y) {
        MST[count++] = edge;
        unionSet(parent, x, y);
        if (count == G->n - 1) {
            break;
        }
    } else {
        edges[i--] = edges[--(*n)];  // 删除边
    }
}

}

// 查找并查集中元素所在的集合 int find(int* parent, int i) { if (parent[i] == i) { return i; } return find(parent, parent[i]); }

// 合并两个集合 void unionSet(int* parent, int x, int y) { int xset = find(parent, x); int yset = find(parent, y); parent[xset] = yset; }