Prim普里姆算法详解与C语言代码实现

Noah

发布时间：2026-10-13| 6人浏览过

原创

Prim算法是求解加权连通图最小生成树（MST）的经典算法之一。它通过逐步扩展顶点集合来构建一棵总权值最小的树，特别适合稠密图的场景。本文将解析其数学原理、数据结构设计，并给出可直接运行的C语言示例。

算法原理与核心概念

最小生成树（Minimum Spanning Tree, MST）是指在一个连通的加权图中，选取 $n-1$ 条边使所有 $n$ 个顶点连通，且这些边的权值之和最小。构造MST需满足两个条件：一是尽可能选取权值小的边；二是确保不形成回路。

Prim算法的核心思想：
从图中任意一个顶点开始，将该顶点加入已选顶点集合 $U$。在所有连接 $U$ 中顶点与 $V-U$（未选顶点集合）中顶点的边中，选择权值最小的一条边，并将该边对面的顶点加入 $U$。重复此过程，直到所有顶点都加入 $U$。此时，所选的 $n-1$ 条边即为最小生成树。

MST性质：
假设 $G=(V,E)$ 是一个连通网，$U$ 是顶点 $V$ 的一个非空子集。若 $(u,v)$ 是一条具有最小权值的边，其中 $u \in U, v \in V-U$，则必存在一棵包含边 $(u,v)$ 的最小生成树。
这一性质保证了Prim算法每一步选择的局部最优边，最终能构成全局最优解。

算法步骤与数据结构

为了高效实现Prim算法，通常使用邻接矩阵存储图结构，并引入两个辅助数组：lowcost 和 closedge。

lowcost[i]：记录顶点 $i$ 到当前生成树集合的最短距离（即最小权值）。
closedge[i]：记录顶点 $i$ 在生成树集合中相邻的顶点索引。

具体操作步骤：

初始化：选择起始顶点（如顶点0），将其标记为已访问。初始化 lowcost 数组为起始点到其他各点的距离，closedge 设为0。
寻找最近点：在未访问的顶点中，找出 lowcost 值最小的顶点 $j$。
并入集合：将顶点 $j$ 标记为已访问，输出或保存边 $(j, closedge[j])$ 及其权值。
更新距离：以新加入的顶点 $j$ 为跳板，检查其对其他未访问顶点 $k$ 的距离。如果 $G[j][k] < lowcost[k]$，则更新 lowcost[k] = G[j][k] 且 closedge[k] = j。
循环：重复步骤2-4，直至所有顶点被访问。

由于每次都需要遍历所有未访问点来找最小值，且没有针对稀疏图优化的优先队列，Prim算法的时间复杂度为 $O(n^2)$。这使得它在顶点数较少或边数密集的稠密图中表现优异，相比之下，Kruskal算法更适合稀疏图。

C语言完整实现

以下示例代码展示了如何使用C语言实现Prim算法。程序从文件读取边信息构建邻接矩阵，并计算最小生成树的总权值。

第1步：准备测试数据文件

创建一个名为 prim.txt 的文件，内容格式为“起点终点权值”（注意：示例中顶点编号从1开始，代码内部会转换为从0开始的索引）：

第2步：编写C语言源代码

将以下代码保存为 prim.c。代码中定义了宏常量以适配最大节点数和无穷大值，主函数负责加载数据并调用核心算法。

#include<stdio.h>
#include<string.h>
#include <stdlib.h>
 
#define INFINITY 1000000 // 定义无穷大，表示两点间无边相连
#define MAX_VERTICES 6   // 定义图形中最大顶点个数
 
typedef int Graph[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵类型
 
void prim(Graph G, int vcount, int father[]) {
    int i, j, k;
    int lowcost[MAX_VERTICES];     // 记录最小代价
    int closedge[MAX_VERTICES];    // 记录依附在U中的顶点
    int used[MAX_VERTICES];        // 标记是否已被选中
    int min_val;
    int result = 0;                // 记录最小生成树的总权值
 
    // 初始化：从顶点0开始
    for (i = 0; i < vcount; i++) {
        lowcost[i] = G[0][i];      // 初始化为到起点0的距离
        closedge[i] = 0;           // 初始依附于0
        used[i] = 0;               // 未访问标记
        father[i] = -1;            // 父节点置为-1
    }
    used[0] = 1;                   // 标记起点0已访问
 
    // 需要再加入 vcount-1 个顶点
    for (i = 1; i <= vcount - 1; i++) {
        min_val = INFINITY;
        j = -1;
 
        // 在未访问顶点中找到离当前生成树最近的顶点j
        for (k = 1; k < vcount; k++) {
            if ((!used[k]) && (lowcost[k] < min_val)) {
                min_val = lowcost[k];
                j = k;
            }
        }
 
        // 如果找不到可达点且min_val仍为无穷大，说明图不连通
        if (j == -1) break;
 
        // 记录路径来源
        father[j] = closedge[j];
        printf("Edge: %d -- %d, Weight: %d\n", j + 1, father[j] + 1, min_val);
        result += min_val;
        
        used[j] = 1;               // 将j并入集合U
 
        // 更新新加入顶点j对其他未访问顶点的距离
        for (k = 1; k < vcount; k++) {
            if (!used[k] && G[j][k] < lowcost[k]) {
                lowcost[k] = G[j][k];
                closedge[k] = j;
            }
        }
    }
    printf("Total MST Weight: %d\n", result);
}
        
int main() {
    FILE *fr;
    int i, j, weight;
    Graph G;
    int father[MAX_VERTICES];
    
    // 初始化邻接矩阵为无穷大
    for(i = 0; i < MAX_VERTICES; i++)
        for(j = 0; j < MAX_VERTICES; j++)
            G[i][j] = INFINITY;
            
    // 读取数据文件
    fr = fopen("prim.txt", "r");
    if (!fr) {
        printf("File open failed. Please check prim.txt exists.\n");
        return 1;
    }
    
    // 填充邻接矩阵（输入为1-based索引，转为0-based）
    while(fscanf(fr, "%d%d%d", &i, &j, &weight) != EOF) {
        G[i-1][j-1] = weight;
        G[j-1][i-1] = weight;      // 无向图，对称赋值
    }
    fclose(fr);
 
    // 执行Prim算法
    prim(G, MAX_VERTICES, father);
 
    return 0;
}