C语言实现Prim与Kruskal最小生成树算法详解

算法核心逻辑解析

第1步：理解Prim算法（普里姆算法）的运行机制

Prim算法的核心在于“加点法”。它从一个起始顶点开始，每次选择连接当前已选顶点集合与未选顶点集合中权值最小的边，将对应的未选顶点加入集合，直至所有顶点都被包含。为了高效实现，通常使用两个辅助数组：

• lowcost[i]：记录以i为终点的边的最小权值。初始时设为起点到各顶点的距离。当该值为0时，表示顶点i已加入生成树。
• mst[i]：记录lowcost[i]所对应的起点下标，用于还原具体的边结构。

由于默认第一个节点（下标1）已加入生成树，后续寻找最短边时需从下标2开始遍历。

第2步：理解Kruskal算法（克鲁斯卡尔算法）的运行机制

Kruskal算法的核心在于“加边法”。它将所有边按权值从小到大排序，依次尝试添加。关键判断条件是：如果某条边连接的两个顶点目前不属于同一个连通分量，则添加该边；否则会产生环路，跳过。这一过程通常借助并查集（或文中简化版的vset数组）来管理顶点的归属集合。

Prim算法的C语言完整实现

以下为经典的朴素版Prim算法实现。代码首先初始化邻接矩阵，然后读取图的节点数和边数，构建无向图结构。

数据结构与初始化

定义最大节点数常量与无穷大常量，使用二维数组graph[MAX][MAX]存储邻接矩阵。初始化时将矩阵置为无穷大，随后根据输入的边填充对应位置及其对称位置（因为是无向图）。

#include <stdio.h>
#include <stdlib.h>
 
#define MAX 100
#define MAXCOST 0x7fffffff // 表示无穷大
 
int graph[MAX][MAX];
 
/* Prim函数主体 */
int Prim(int graph[][MAX], int n)
{
    /* lowcost[i]记录以i为终点的边的最小权值，=0表示已加入 */
    int lowcost[MAX];
    /* mst[i]记录对应lowcost[i]的起点下标 */
    int mst[MAX];
    int i, j, min, minid, sum = 0;
 
    /* 1. 初始化：默认1号节点已在树中 */
    for (i = 2; i <= n; i++)
    {
        lowcost[i] = graph[1][i]; // 初始化为1号节点到其他节点的距离
        mst[i] = 1;               // 标记边的起点均为1号节点
    }
    mst[1] = 0;                   // 标记1号节点已加入生成树
 
    /* 2. 主循环：还需要加入n-1个节点 */
    for (i = 2; i <= n; i++)
    {
        min = MAXCOST;
        minid = 0;
 
        /* 2.1 在所有未加入节点中寻找权值最小的边 */
        for (j = 2; j <= n; j++)
        {
            if (lowcost[j] < min && lowcost[j] != 0)
            {
                min = lowcost[j];
                minid = j;
            }
        }
 
        /* 2.2 输出生成树边的信息: 起点字符 - 终点字符 : 权值 */
        printf("%c - %c : %d\n", mst[minid] + 'A' - 1, minid + 'A' - 1, min);
        sum += min;       // 累加权值
        lowcost[minid] = 0; // 标记节点minid已加入生成树
 
        /* 2.3 更新其他节点到生成树的最小权值 */
        for (j = 2; j <= n; j++)
        {
            if (graph[minid][j] < lowcost[j])
            {
                lowcost[j] = graph[minid][j]; // 发现更小权值，更新
                mst[j] = minid;               // 更新边的起点
            }
        }
    }
    return sum;
}
 
int main()
{
    int i, j, k, m, n;
    int x, y, cost;
    char chx, chy;
 
    /* 读取节点数m和边数n */
    scanf("%d%d", &m, &n);
    getchar(); // 清理换行符
 
    /* 初始化图，距离设为无穷大 */
    for (i = 1; i <= m; i++)
    {
        for (j = 1; j <= m; j++)
        {
            graph[i][j] = MAXCOST;
        }
    }
 
    /* 读取边的信息并填入邻接矩阵 */
    for (k = 0; k < n; k++)
    {
        scanf("%c %c %d", &chx, &chy, &cost);
        getchar(); // 清理换行符
        i = chx - 'A' + 1;   // 将字符转为数字索引(A->1)
        j = chy - 'A' + 1;
        graph[i][j] = cost;  // 有向赋值
        graph[j][i] = cost;  // 无向赋值
    }
 
    /* 调用Prim算法求解 */
    cost = Prim(graph, m);
 
    /* 输出总权值和 */
    printf("Total:%d\n", cost);
    return 0;
}

Kruskal算法的C语言实现

Kruskal的实现相对简洁，但通常需要配合排序算法和边结构体。以下展示基于辅助数组vset的版本，该版本演示了集合合并的基本逻辑。

void Kruskal(Edge E[], int n, int e) // E为边数组, n为顶点数, e为边数
{
    int i, j, m1, m2, sn1, sn2, k;
    int vset[MAXE];
 
    /* 初始化每个顶点属于不同的集合，编号即其自身下标 */
    for (i = 0; i < n; i++)
    {
        vset[i] = i;
    }
 
    k = 1; // 当前构造最小生成树的第几条边
    j = 0; // E数组中的下标
 
    while (k < n) // 只要生成的边数小于n就继续
    {
        /* 取一条边，获取其头尾顶点 */
        m1 = E[j].u;
        m2 = E[j].v;
 
        /* 查找这两个顶点所属的集合编号 */
        sn1 = vset[m1];
        sn2 = vset[m2];
 
        /* 如果不在同一集合，说明加入这条边不会形成环，选中它 */
        if (sn1 != sn2)
        {
            printf(" (%d,%d):%d/n", m1, m2, E[j].w);
            k++; // 选中的边数量+1
 
            /* 合并两个集合：将所有属于sn2的顶点的集合编号改为sn1 */
            for (i = 0; i < n; i++)
            {
                if (vset[i] == sn2)
                {
                    vset[i] = sn1;
                }
            }
        }
        j++; // 扫描下一条边
    }
}

测试验证与结果分析

以一段包含7个节点和11条边的带权无向图为例进行验证。输入数据中字母代表顶点（A-G），数值代表边的权重。

输入示例：

7 11
A B 7
A D 5
B C 8
B D 9
B E 7
C E 5
D E 15
D F 6
E F 8
E G 9
F G 11

Pri算法输出示例：

A - D : 5
D - F : 6
A - B : 7
B - E : 7
E - C : 5
E - G : 9
Total:39

结果表明，最小生成树的总权值和为39，算法正确找到了所有必要边且无环路。在实际开发中，对于边数密集的稠密图，建议使用Prim算法的时间复杂度表现较好；而在稀疏图中，结合排序优化的Kruskal算法往往更具优势。

以上就是C语言实现最小生成树（Prim与Kruskal算法）的详细内容，更多关于C语言图论算法的资料请关注本站其它相关文章！