c prim算法求最小生成树

C语言中的Prim算法可以用来求解带权图的最小生成树。Prim算法采用贪心算法的思想，每次从连通网中找出一个权值最小的边，这样的操作重复N-1次，由N-1条权值最小的边组成的生成树就是最小生成树MST（Minimum Spanning Tree，最小生成树）。具体实现过程如下：
1. 选取一个起始点，将其加入生成树中。
2. 找到与生成树相邻的所有边中权值最小的边，将其加入生成树中。
3. 重复第二步，直到生成树中包含了所有的顶点。

C语言中Prim算法的实现需要使用到优先队列，可以使用堆来实现。具体实现过程可以参考以下代码：

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

#define MAX_VERTICES 1000

typedef struct {
    int v;
    int weight;
} Edge;

typedef struct {
    Edge* edges[MAX_VERTICES];
    int size[MAX_VERTICES];
    int capacity[MAX_VERTICES];
} Graph;

typedef struct {
    int* data;
    int size;
    int capacity;
} Heap;

Graph* createGraph(int n) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    for (int i = 0; i < n; i++) {
        graph->size[i] = 0;
        graph->capacity[i] = 1;
        graph->edges[i] = (Edge*)malloc(sizeof(Edge) * graph->capacity[i]);
    }
    return graph;
}

void addEdge(Graph* graph, int u, int v, int weight) {
    if (graph->size[u] == graph->capacity[u]) {
        graph->capacity[u] *= 2;
        graph->edges[u] = (Edge*)realloc(graph->edges[u], sizeof(Edge) * graph->capacity[u]);
    }
    graph->edges[u][graph->size[u]].v = v;
    graph->edges[u][graph->size[u]].weight = weight;
    graph->size[u]++;
}

Heap* createHeap(int capacity) {
    Heap* heap = (Heap*)malloc(sizeof(Heap));
    heap->data = (int*)malloc(sizeof(int) * capacity);
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void push(Heap* heap, int value) {
    heap->data[heap->size] = value;
    int current = heap->size;
    int parent = (current - 1) / 2;
    while (current > 0 && heap->data[current] < heap->data[parent]) {
        swap(&heap->data[current], &heap->data[parent]);
        current = parent;
        parent = (current - 1) / 2;
    }
    heap->size++;
}

int pop(Heap* heap) {
    int result = heap->data[0];
    heap->size--;
    heap->data[0] = heap->data[heap->size];
    int current = 0;
    while (1) {
        int left = current * 2 + 1;
        int right = current * 2 + 2;
        int smallest = current;
        if (left < heap->size && heap->data[left] < heap->data[smallest]) {
            smallest = left;
        }
        if (right < heap->size && heap->data[right] < heap->data[smallest]) {
            smallest = right;
        }
        if (smallest == current) {
            break;
        }
        swap(&heap->data[current], &heap->data[smallest]);
        current = smallest;
    }
    return result;
}

int prim(Graph* graph, int n) {
    int* visited = (int*)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        visited[i] = 0;
    }
    Heap* heap = createHeap(n);
    push(heap, 0);
    int result = 0;
    while (heap->size > 0) {
        int u = pop(heap);
        if (visited[u]) {
            continue;
        }
        visited[u] = 1;
        result += heap->data[u];
        for (int i = 0; i < graph->size[u]; i++) {
            int v = graph->edges[u][i].v;
            int weight = graph->edges[u][i].weight;
            if (!visited[v]) {
                push(heap, weight);
            }
        }
    }
    free(visited);
    free(heap->data);
    free(heap);
    return result;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    Graph* graph = createGraph(n);
    for (int i = 0; i < m; i++) {
        int u, v, weight;
        scanf("%d%d%d", &u, &v, &weight);
        addEdge(graph, u, v, weight);
        addEdge(graph, v, u, weight);
    }
    int result = prim(graph, n);
    printf("%d\n", result);
    return 0;
}