最小生成树prim C语言

以下是Prim算法的C语言实现，假设图的顶点数为n，边数为m，使用邻接矩阵表示图：

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

#define MAX_VERTEX_NUM 100
#define INF INT_MAX

typedef struct {
    int vertex[MAX_VERTEX_NUM];  // 顶点集合
    int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 邻接矩阵
    int n, e;  // 顶点数、边数
} Graph;

void createGraph(Graph* G) {
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G->n, &G->e);

    printf("请输入顶点信息：");
    for (int i = 1; i <= G->n; ++i) {
        scanf("%d", &G->vertex[i]);
    }

    // 初始化邻接矩阵
    for (int i = 1; i <= G->n; ++i) {
        for (int j = 1; j <= G->n; ++j) {
            G->edge[i][j] = INF;
        }
    }

    // 输入边的信息
    printf("请输入边的信息：\n");
    for (int k = 1; k <= G->e; ++k) {
        int i, j, w;
        scanf("%d%d%d", &i, &j, &w);
        G->edge[i][j] = G->edge[j][i] = w;  // 无向图
    }
}

void prim(Graph* G, int v) {
    bool visited[MAX_VERTEX_NUM] = {false};  // 标记顶点是否已加入生成树
    int dist[MAX_VERTEX_NUM];  // 存储最短距离
    int parent[MAX_VERTEX_NUM];  // 存储生成树的父节点
    for (int i = 1; i <= G->n; ++i) {
        dist[i] = INF;
        parent[i] = -1;
    }

    dist[v] = 0;  // 起点到自身的距离为0
    for (int i = 1; i <= G->n; ++i) {
        // 找到未加入生成树的距离最短的点
        int u = -1, minDist = INF;
        for (int j = 1; j <= G->n; ++j) {
            if (!visited[j] && dist[j] < minDist) {
                u = j;
                minDist = dist[j];
            }
        }

        if (u == -1) {
            break;  // 所有顶点都已加入生成树
        }

        visited[u] = true;
        for (int j = 1; j <= G->n; ++j) {
            if (!visited[j] && G->edge[u][j] < dist[j]) {
                dist[j] = G->edge[u][j];
                parent[j] = u;
            }
        }
    }

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

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

    int v;
    printf("请输入起点：");
    scanf("%d", &v);

    prim(&G, v);
    
    return 0;
}

在该实现中，使用了一个dist数组存储每个顶点到当前生成树的距离，使用一个parent数组存储生成树的父节点。使用一个visited数组标记每个顶点是否已加入生成树。在每次循环中，找到未加入生成树的距离最短的点u，将它加入生成树，并更新dist和parent数组。最后输出生成树即可。