普利姆最小生成树算法代码实现c语言

普利姆（Prim's Algorithm）是最小生成树算法的一种，它是一种贪心算法，用于寻找加权无向图中的最小生成树。在C语言中实现这个算法，我们需要用到优先队列数据结构来存储边，并且从一个起点开始逐步添加边，确保每一步都连接上当前树中没有到达的节点并保持总权重最小。

以下是基本的C语言实现：

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

// 定义图的数据结构
typedef struct {
    int src, dest, weight;
} Edge;

// 比较两个边的权重
int compare_edges(const void *a, const void *b) {
    Edge *edge1 = (Edge *)a;
    Edge *edge2 = (Edge *)b;
    return edge1->weight - edge2->weight;
}

// 初始化优先队列
typedef struct {
    Edge *edges;
    int size, capacity;
} PriorityQueue;

void init_priority_queue(PriorityQueue *pq, int capacity) {
    pq->edges = malloc(capacity * sizeof(Edge));
    pq->size = 0;
    pq->capacity = capacity;
}

// 入队
void enqueue(PriorityQueue *pq, Edge e) {
    if (pq->size == pq->capacity) {
        pq->capacity *= 2;
        pq->edges = realloc(pq->edges, pq->capacity * sizeof(Edge));
    }
    pq->edges[pq->size++] = e;
}

// 出队
Edge dequeue(PriorityQueue *pq) {
    if (pq->size == 0)
        return (Edge){-1, -1, INT_MAX};
    Edge min_edge = pq->edges[0];
    pq->edges = pq->edges[--pq->size];
    return min_edge;
}

// Prim's algorithm
void prim_minimum_spanning_tree(int graph[][V], int V, int E, Edge *result, int *visited) {
    PriorityQueue pq;
    init_priority_queue(&pq, E);
    
    result.src = 0; // 选择任意一个节点作为起点
    visited = 1;
    enqueue(&pq, (Edge){0, graph, graph});

    for (int i = 1; i < V; ++i) {
        Edge min_edge = dequeue(&pq);

        // 找到所有与当前节点相连且未访问的节点
        for (int j = 0; j < V; ++j) {
            if (!visited[j] && graph[min_edge.dest][j] && min_edge.weight < graph[min_edge.src][j]) {
                min_edge.src = min_edge.dest;
                min_edge.dest = j;
                min_edge.weight = graph[min_edge.dest][j];
                enqueue(&pq, min_edge);
            }
        }

        result[i] = min_edge;
        visited[min_edge.dest] = 1;
    }
}

int main() {
    int V, E;
    // 假设输入为V、E和图的邻接矩阵graph[V][V]
    // 例如：V = 4, E = 6, graph类似这样：
    //   0 1 2 3
    // 0: 0 4 0 0
    // 1: 4 0 8 0
    // 2: 0 8 0 11
    // 3: 0 0 11 0
    prim_minimum_spanning_tree(graph, V, E, result, visited);
    // ...然后处理结果数组result，它包含了最小生成树的所有边
    return 0;
}