c语言用普里姆算法实现图的最小生成树

普里姆算法是一种基于贪心思想的图论算法，用于求解一个带权无向图的最小生成树。

以下是用C语言实现普里姆算法求解图的最小生成树的基本步骤：

1. 定义一个结构体来表示边，包含边的起点、终点和边权值。

struct Edge {
    int v, w; // 终点和边权值
};

2. 定义一个小根堆，存储当前已经加入最小生成树中的节点的所有出边。

typedef struct {
    int v, w; // 节点编号和边权值
} HeapNode;

HeapNode heap[MAXN]; // 小根堆数组，用于存储当前已经加入最小生成树中的节点的所有出边
int size = 0; // 小根堆的大小

void push(int v, int w) { // 向小根堆中加入一个节点的出边
    heap[size].v = v;
    heap[size].w = w;
    size++;
    int i = size - 1;
    while (i > 0) {
        int p = (i - 1) / 2;
        if (heap[p].w > heap[i].w) {
            HeapNode t = heap[p];
            heap[p] = heap[i];
            heap[i] = t;
            i = p;
        } else {
            break;
        }
    }
}

HeapNode pop() { // 从小根堆中弹出权值最小的边
    HeapNode res = heap[0];
    heap[0] = heap[size - 1];
    size--;
    int i = 0;
    while (i * 2 + 1 < size) {
        int l = i * 2 + 1;
        int r = i * 2 + 2;
        int j = l;
        if (r < size && heap[l].w > heap[r].w) {
            j = r;
        }
        if (heap[i].w > heap[j].w) {
            HeapNode t = heap[i];
            heap[i] = heap[j];
            heap[j] = t;
            i = j;
        } else {
            break;
        }
    }
    return res;
}

3. 定义一个数组dist，用于存储每个节点距离最小生成树的距离。

int dist[MAXN]; // dist[i]表示节点i距离最小生成树的距离

4. 定义一个函数，用于求解最小生成树。

void prim(int n, int m, Edge edges[][MAXN], int s) { // n为节点数，m为边数，edges为邻接矩阵，s为起点
    int ans = 0; // 最小生成树的权值和
    memset(dist, 0x3f, sizeof(dist)); // 初始化dist数组为无穷大
    dist[s] = 0; // 起点到自己的距离为0
    push(s, 0); // 将起点加入小根堆中
    while (size > 0) { // 当小根堆不为空时
        HeapNode node = pop(); // 弹出权值最小的边
        int v = node.v, w = node.w;
        if (dist[v] < w) { // 如果当前节点已经加入最小生成树中，则跳过
            continue;
        }
        ans += w; // 计算最小生成树的权值和
        dist[v] = 0; // 将当前节点加入最小生成树中
        for (int i = 1; i <= n; i++) { // 枚举当前节点的所有出边
            if (edges[v][i].w < INF && dist[i] > edges[v][i].w) { // 如果当前节点到i的距离比已知的距离更小，则将i加入小根堆中
                dist[i] = edges[v][i].w;
                push(i, dist[i]);
            }
        }
    }
    printf("%d\n", ans); // 输出最小生成树的权值和
}

完整代码如下：