如何用C语言实现最小生成树算法？

最小生成树是指在一个连通无向带权图中，选取若干条边连接所有顶点，且这些边不构成环，同时边权总和最小。在C语言中，我们通常先用邻接矩阵描述图，再用Prim或Kruskal算法求解。下面是一张示意图。

图的存储结构

使用二维数组存放顶点间的边权，若两点不连通则记为很大的数，例如INF。

#include <stdio.h>
#define V 5
#define INF 99999

// 邻接矩阵表示的图
int graph[V][V] = {
    {0, 2, INF, 6, INF},
    {2, 0, 3, 8, 5},
    {INF, 3, 0, INF, 7},
    {6, 8, INF, 0, 9},
    {INF, 5, 7, 9, 0}
};

int main() {
    // 此处仅展示图的定义，算法在后面实现
    return 0;
}

Prim算法实现

Prim算法从某个起点开始，每次选择与当前生成树相连且权值最小的边，加入树中。

#include <stdio.h>
#define V 5
#define INF 99999

int minKey(int key[], int mstSet[]) {
    int min = INF, min_index;
    for (int v = 0; v < V; v++) {
        if (mstSet[v] == 0 && key[v] < min) {
            min = key[v];
            min_index = v;
        }
    }
    return min_index;
}

void prim(int graph[V][V]) {
    int parent[V];
    int key[V];
    int mstSet[V];
    for (int i = 0; i < V; i++) {
        key[i] = INF;
        mstSet[i] = 0;
    }
    key[0] = 0;
    parent[0] = -1;
    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet);
        mstSet[u] = 1;
        for (int v = 0; v < V; v++) {
            if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }
    printf("边  权值n");
    for (int i = 1; i < V; i++) {
        printf("%d - %d  %dn", parent[i], i, graph[i][parent[i]]);
    }
}

int main() {
    int graph[V][V] = {
        {0, 2, INF, 6, INF},
        {2, 0, 3, 8, 5},
        {INF, 3, 0, INF, 7},
        {6, 8, INF, 0, 9},
        {INF, 5, 7, 9, 0}
    };
    prim(graph);
    return 0;
}

Kruskal算法实现

Kruskal算法先对所有边按权值排序，再依次加入不形成环的边，常用并查集判断连通性。

#include <stdio.h>
#include <stdlib.h>
#define V 5
#define E 7

struct Edge {
    int u, v, w;
};

int find(int parent[], int i) {
    if (parent[i] == i) return i;
    return parent[i] = find(parent, parent[i]);
}

void unionSet(int parent[], int rank[], int x, int y) {
    int rx = find(parent, x);
    int ry = find(parent, y);
    if (rank[rx] < rank[ry]) parent[rx] = ry;
    else if (rank[rx] > rank[ry]) parent[ry] = rx;
    else {
        parent[ry] = rx;
        rank[rx]++;
    }
}

int cmp(const void* a, const void* b) {
    return ((struct Edge*)a)->w - ((struct Edge*)b)->w;
}

void kruskal(struct Edge edges[]) {
    int parent[V], rank[V];
    for (int i = 0; i < V; i++) {
        parent[i] = i;
        rank[i] = 0;
    }
    qsort(edges, E, sizeof(edges[0]), cmp);
    printf("边  权值n");
    int count = 0, i = 0;
    while (count < V - 1 && i < E) {
        int x = find(parent, edges[i].u);
        int y = find(parent, edges[i].v);
        if (x != y) {
            printf("%d - %d  %dn", edges[i].u, edges[i].v, edges[i].w);
            unionSet(parent, rank, x, y);
            count++;
        }
        i++;
    }
}

int main() {
    struct Edge edges[E] = {
        {0,1,2},{0,3,6},{1,2,3},
        {1,3,8},{1,4,5},{2,4,7},{3,4,9}
    };
    kruskal(edges);
    return 0;
}

两种算法比较

在C语言最小生成树实现中，Prim更适合稠密图，Kruskal更适合稀疏图。实际开发可根据图的边数和顶点数选择。

通过上述代码，我们完成了C语言最小生成树的基本实现，读者可在本地编译器上验证结果。

C语言最小生成树Prim算法Kruskal算法图结构修改时间：2026-07-24 20:42:27