最小生成树 C语言实现

// Prim算法实现最小生成树
#include <stdio.h>
#include <limits.h>

// 定义顶点数和边数的最大值
#define MAX_VERTICES 100
#define INF INT_MAX

// 定义图的结构体
typedef struct {
    int n; // 顶点数
    int m; // 边数
    int edges[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
} Graph;

// Prim算法实现
void prim(Graph* G, int v0, int parent[]) {
    int lowcost[MAX_VERTICES]; // 存放当前顶点到生成树集合的最小权值
    int closest[MAX_VERTICES]; // 存放当前顶点到生成树集合中的最近顶点

    // 初始化lowcost和closest数组
    for (int i = 0; i < G->n; i++) {
        lowcost[i] = G->edges[v0][i];
        closest[i] = v0;
    }
    lowcost[v0] = 0;

    // 将v0加入生成树集合
    parent[v0] = -1;

    for (int i = 1; i < G->n; i++) {
        int min = INF;
        int k = -1;
        // 选择lowcost中的最小值
        for (int j = 0; j < G->n; j++) {
            if (lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
        }
        // 将k加入生成树集合
        parent[k] = closest[k];
        lowcost[k] = 0;

        // 更新lowcost和closest数组
        for (int j = 0; j < G->n; j++) {
            if (G->edges[k][j] < lowcost[j]) {
                lowcost[j] = G->edges[k][j];
                closest[j] = k;
            }
        }
    }
}

int main() {
    Graph G;
    int parent[MAX_VERTICES]; // 存放最小生成树的边

    // 初始化图的顶点数和边数
    G.n = 6;
    G.m = 9;

    // 初始化邻接矩阵
    int edges[6][6] = {
        {0, 6, 1, 5, INF, INF},
        {6, 0, 5, INF, 3, INF},
        {1, 5, 0, 5, 6, 4},
        {5, INF, 5, 0, INF, 2},
        {INF, 3, 6, INF, 0, 6},
        {INF, INF, 4, 2, 6, 0}
    };
    for (int i = 0; i < G.n; i++) {
        for (int j = 0; j < G.n; j++) {
            G.edges[i][j] = edges[i][j];
        }
    }

    // 调用Prim算法
    prim(&G, 0, parent);

    // 输出最小生成树的边
    for (int i = 1; i < G.n; i++) {
        printf("%d - %d\n", parent[i], i);
    }

    return 0;
}