用C语言编写普利姆算法邻接表的代码

下面是使用C语言实现Prim算法的邻接表代码：

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

#define MAX_VERTICES 1000

typedef struct edge {
    int dest;
    int weight;
    struct edge* next;
} edge_t;

typedef struct vertex {
    edge_t* edges;
    int visited;
    int key;
    int parent;
} vertex_t;

typedef struct graph {
    vertex_t vertices[MAX_VERTICES];
    int vertex_count;
} graph_t;

graph_t* create_graph() {
    graph_t* graph = (graph_t*) malloc(sizeof(graph_t));
    graph->vertex_count = 0;
    return graph;
}

void add_vertex(graph_t* graph) {
    if (graph->vertex_count < MAX_VERTICES) {
        graph->vertices[graph->vertex_count].edges = NULL;
        graph->vertices[graph->vertex_count].visited = 0;
        graph->vertices[graph->vertex_count].key = INT_MAX;
        graph->vertices[graph->vertex_count].parent = -1;
        graph->vertex_count++;
    }
}

void add_edge(graph_t* graph, int src, int dest, int weight) {
    if (src >= 0 && src < graph->vertex_count && dest >= 0 && dest < graph->vertex_count) {
        edge_t* edge = (edge_t*) malloc(sizeof(edge_t));
        edge->dest = dest;
        edge->weight = weight;
        edge->next = graph->vertices[src].edges;
        graph->vertices[src].edges = edge;

        edge = (edge_t*) malloc(sizeof(edge_t));
        edge->dest = src;
        edge->weight = weight;
        edge->next = graph->vertices[dest].edges;
        graph->vertices[dest].edges = edge;
    }
}

void prim(graph_t* graph) {
    int i, j, u, v;
    int min_distance, weight;
    for (i = 1; i < graph->vertex_count; i++) {
        graph->vertices[i].key = INT_MAX;
        graph->vertices[i].visited = 0;
    }

    graph->vertices[0].key = 0;
    graph->vertices[0].parent = -1;

    for (i = 0; i < graph->vertex_count - 1; i++) {
        u = -1;
        min_distance = INT_MAX;
        for (j = 0; j < graph->vertex_count; j++) {
            if (!graph->vertices[j].visited && graph->vertices[j].key < min_distance) {
                u = j;
                min_distance = graph->vertices[j].key;
            }
        }

        graph->vertices[u].visited = 1;

        edge_t* edge = graph->vertices[u].edges;
        while (edge != NULL) {
            v = edge->dest;
            weight = edge->weight;
            if (!graph->vertices[v].visited && weight < graph->vertices[v].key) {
                graph->vertices[v].parent = u;
                graph->vertices[v].key = weight;
            }
            edge = edge->next;
        }
    }
}

void print_graph(graph_t* graph) {
    int i;
    for (i = 1; i < graph->vertex_count; i++) {
        printf("Vertex %d -> Parent %d Weight %d\n", i, graph->vertices[i].parent, graph->vertices[i].key);
    }
}

void free_graph(graph_t* graph) {
    int i;
    edge_t* edge, * temp;
    for (i = 0; i < graph->vertex_count; i++) {
        edge = graph->vertices[i].edges;
        while (edge != NULL) {
            temp = edge;
            edge = edge->next;
            free(temp);
        }
    }
    free(graph);
}

int main() {
    graph_t* graph = create_graph();

    add_vertex(graph);
    add_vertex(graph);
    add_vertex(graph);
    add_vertex(graph);
    add_vertex(graph);

    add_edge(graph, 0, 1, 2);
    add_edge(graph, 0, 3, 6);
    add_edge(graph, 1, 2, 3);
    add_edge(graph, 1, 3, 8);
    add_edge(graph, 1, 4, 5);
    add_edge(graph, 2, 4, 7);
    add_edge(graph, 3, 4, 9);

    prim(graph);

    print_graph(graph);

    free_graph(graph);

    return 0;
}