C语言普里姆算法输出最小生成树

普里姆（Prim）算法是一种用于构建最小生成树的贪心算法。它的基本思路是从任意一个顶点开始，每次往最小权值的边所连接的顶点扩展，直到所有顶点都被遍历。下面是C语言实现Prim算法输出最小生成树的代码：

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

#define MAXVEX 100
#define INF 65535

typedef struct EdgeNode {
    int adjvex; // 邻接点序号
    int weight; // 权值
    struct EdgeNode *next; // 指向下一条边的指针
} EdgeNode;

typedef struct VertexNode {
    char data; // 顶点信息
    EdgeNode *firstedge; // 指向第一条边的指针
} VertexNode, AdjList[MAXVEX];

typedef struct {
    AdjList adjList;
    int numVertexes, numEdges; // 图中当前顶点数和边数
} GraphAdjList;

void CreateGraph(GraphAdjList *G) {
    int i, j, k, w;
    EdgeNode *e;

    printf("请输入顶点数和边数：\n");
    scanf("%d%d", &G->numVertexes, &G->numEdges);

    for (i = 0; i < G->numVertexes; i++) {
        printf("请输入第%d个顶点的信息：", i + 1);
        scanf(" %c", &G->adjList[i].data);
        G->adjList[i].firstedge = NULL; // 初始化邻接表
    }

    for (k = 0; k < G->numEdges; k++) {
        printf("请输入边(vi, vj)上的下标i, j和权值w：\n");
        scanf("%d%d%d", &i, &j, &w);

        // 添加边(i, j)
        e = (EdgeNode*)malloc(sizeof(EdgeNode));
        e->adjvex = j;
        e->weight = w;
        e->next = G->adjList[i].firstedge;
        G->adjList[i].firstedge = e;

        // 添加边(j, i)
        e = (EdgeNode*)malloc(sizeof(EdgeNode));
        e->adjvex = i;
        e->weight = w;
        e->next = G->adjList[j].firstedge;
        G->adjList[j].firstedge = e;
    }
}

void MiniSpanTree_Prim(GraphAdjList *G, int start) {
    int min, i, j, k;
    int adjvex[MAXVEX]; // 存放顶点下标
    int lowcost[MAXVEX]; // 存放边的权值
    lowcost[start] = 0; // 初始化第一个权值为0，即v0加入生成树
    adjvex[start] = 0; // 初始化第一个顶点下标为0

    // 初始化lowcost和adjvex数组
    for (i = 1; i < G->numVertexes; i++) {
        lowcost[i] = INF;
        adjvex[i] = start;
    }

    for (i = 1; i < G->numVertexes; i++) {
        min = INF;
        j = 0;
        k = 0;

        // 找到权值最小的边所连接的顶点
        while (j < G->numVertexes) {
            if (lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
            j++;
        }

        printf("(%c, %c)", G->adjList[adjvex[k]].data, G->adjList[k].data);
        lowcost[k] = 0;

        // 更新lowcost和adjvex数组
        for (j = 0; j < G->numVertexes; j++) {
            if (lowcost[j] != 0 && G->adjList[k].firstedge != NULL && G->adjList[k].firstedge->weight < lowcost[j]) {
                lowcost[j] = G->adjList[k].firstedge->weight;
                adjvex[j] = k;
            }
        }
    }
}

int main() {
    GraphAdjList G;
    int start;

    CreateGraph(&G);

    printf("请输入起始顶点：");
    scanf("%d", &start);

    MiniSpanTree_Prim(&G, start);

    return 0;
}

这段代码中，CreateGraph函数用于创建邻接表存储图，MiniSpanTree_Prim函数实现Prim算法输出最小生成树。其中，lowcost数组存放边的权值，adjvex数组存放顶点下标。如果lowcost[j]为0，则说明顶点j已经加入生成树。