C语言实现最小生成树

以下是使用Prim算法实现最小生成树的C语言代码：

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

#define MAX_VERTICES 1000

typedef struct {
    int start;
    int end;
    int weight;
} Edge;

typedef struct {
    int num_vertices;
    int num_edges;
    Edge edges[MAX_VERTICES];
} Graph;

void prim(Graph* graph, int start) {
    int selected[MAX_VERTICES] = {0};
    int distance[MAX_VERTICES];
    int parent[MAX_VERTICES] = {0};
    int i, j, min_distance, u;

    // 初始化距离和父节点
    for (i = 0; i < graph->num_vertices; i++) {
        distance[i] = INT_MAX;
    }
    parent[start] = -1;
    distance[start] = 0;

    // 选出n-1个节点
    for (i = 0; i < graph->num_vertices - 1; i++) {
        min_distance = INT_MAX;
        // 找到当前未选择节点中距离最近的节点
        for (j = 0; j < graph->num_vertices; j++) {
            if (!selected[j] && distance[j] < min_distance) {
                min_distance = distance[j];
                u = j;
            }
        }
        selected[u] = 1;
        // 更新与该节点相邻节点的距离
        for (j = 0; j < graph->num_edges; j++) {
            if (graph->edges[j].start == u && !selected[graph->edges[j].end] && graph->edges[j].weight < distance[graph->edges[j].end]) {
                parent[graph->edges[j].end] = u;
                distance[graph->edges[j].end] = graph->edges[j].weight;
            }
            else if (graph->edges[j].end == u && !selected[graph->edges[j].start] && graph->edges[j].weight < distance[graph->edges[j].start]) {
                parent[graph->edges[j].start] = u;
                distance[graph->edges[j].start] = graph->edges[j].weight;
            }
        }
    }

    // 输出最小生成树
    printf("Edge   Weight\n");
    for (i = 1; i < graph->num_vertices; i++) {
        printf("%d - %d   %d\n", parent[i], i, distance[i]);
    }
}

int main() {
    Graph graph;
    int i, num_edges, start;

    printf("Enter the number of vertices: ");
    scanf("%d", &graph.num_vertices);

    printf("Enter the number of edges: ");
    scanf("%d", &num_edges);

    graph.num_edges = num_edges;
    for (i = 0; i < num_edges; i++) {
        printf("Enter edge %d (start end weight): ", i + 1);
        scanf("%d %d %d", &graph.edges[i].start, &graph.edges[i].end, &graph.edges[i].weight);
    }

    printf("Enter the starting vertex: ");
    scanf("%d", &start);

    prim(&graph, start);

    return 0;
}

在上述代码中，我们定义了一个结构体`Edge`来表示图中的边，以及一个结构体`Graph`来表示整个图。`prim`函数接受一个`Graph`指针和一个起始节点作为参数，然后实现Prim算法来求解最小生成树，并输出结果。

在`main`函数中，我们先输入图的顶点数和边数，然后输入每条边的起点、终点和权重。最后输入起始节点，并调用`prim`函数来求解最小生成树。