C语言破圈法求带权连通图最小生成树 | 最小生成树算法实现

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

#define MAX_VERTEX_NUM 100 // 最大顶点数 #define INF 0x3f3f3f3f // 无穷大

// 图的邻接矩阵表示 typedef struct { int vertex[MAX_VERTEX_NUM]; // 顶点数组 int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵 int vertex_num; // 顶点数 int edge_num; // 边数 } Graph;

// 初始化图 void init_graph(Graph* G) { int i, j; for (i = 0; i < MAX_VERTEX_NUM; i++) { G->vertex[i] = 0; for (j = 0; j < MAX_VERTEX_NUM; j++) { G->edge[i][j] = INF; } } G->vertex_num = 0; G->edge_num = 0; }

// 添加顶点 void add_vertex(Graph* G, int v) { G->vertex[G->vertex_num++] = v; }

// 添加边 void add_edge(Graph* G, int u, int v, int w) { G->edge[u][v] = w; G->edge[v][u] = w; G->edge_num++; }

// 打印图 void print_graph(Graph G) { int i, j; printf("Graph: "); for (i = 0; i < G.vertex_num; i++) { for (j = 0; j < G.vertex_num; j++) { printf("%10d ", G.edge[i][j]); } printf(" "); } }

// 破圈法求最小生成树 void prim(Graph G) { int i, j, k, min, sum = 0; int lowcost[MAX_VERTEX_NUM]; // 存储点到树的距离 int closest[MAX_VERTEX_NUM]; // 存储最近的点 bool S[MAX_VERTEX_NUM]; // 标记是否在树上

// 初始化最小生成树
for (i = 1; i < G.vertex_num; i++) {
    lowcost[i] = G.edge[0][i];  // 初始化为与0号顶点相邻的边的权值
    closest[i] = 0;  // 初始化最近的点为0号顶点
    S[i] = false;  // 初始化不在树上
}
S[0] = true;  // 将0号顶点加入树中

// 找n-1条边
for (i = 1; i < G.vertex_num; i++) {
    min = INF;
    k = -1;

    // 从不在树上的点中找到到树最近的点
    for (j = 1; j < G.vertex_num; j++) {
        if (!S[j] && lowcost[j] < min) {
            min = lowcost[j];
            k = j;
        }
    }

    // 将k号顶点加入树中，并输出边
    printf("%d - %d\n", closest[k], k);
    sum += min;
    S[k] = true;

    // 更新点到树的距离和最近的点
    for (j = 1; j < G.vertex_num; j++) {
        if (!S[j] && G.edge[k][j] < lowcost[j]) {
            lowcost[j] = G.edge[k][j];
            closest[j] = k;
        }
    }
}

printf("Minimum cost: %d\n", sum);

}

int main() { Graph G; init_graph(&G);

// 添加顶点
add_vertex(&G, 0);
add_vertex(&G, 1);
add_vertex(&G, 2);
add_vertex(&G, 3);
add_vertex(&G, 4);

// 添加边
add_edge(&G, 0, 1, 6);
add_edge(&G, 0, 2, 1);
add_edge(&G, 0, 3, 5);
add_edge(&G, 1, 2, 5);
add_edge(&G, 1, 4, 3);
add_edge(&G, 2, 3, 5);
add_edge(&G, 2, 4, 6);
add_edge(&G, 3, 4, 2);

// 打印图
print_graph(G);

// 破圈法求最小生成树
prim(G);

return 0;

}