Prim算法：从原理到代码，揭秘最小生成树奥秘

一、先搞懂：什么是 Prim 算法？

我们日常会遇到这样的问题：有多个城市（对应图中的 “顶点”），城市间有公路（对应 “边”）且每条公路有造价（对应 “权值”），如何用最低的总造价修公路，让所有城市都连通？这就是 “最小生成树” 问题，而Prim 算法就是解决这个问题的经典方法之一。

简单说，Prim 算法的核心思路的是 “逐步扩张”：从任意一个顶点（比如代码中的 A 点）开始，每次选一条 “连接当前已连通区域和未连通区域” 的最短边，把未连通的顶点纳入已连通区域，重复直到所有顶点都连通。最终选出的边，就构成了总权值最小的生成树。

二、结合代码，看 Prim 算法怎么跑？

提供的 C 语言代码，完美实现了 Prim 算法解决 9 个顶点（A-I）、15 条边的无向图问题。我们一步步拆解核心逻辑：

1. 先搭好图的 “架子”

代码里先定义了图的结构（graph），包含顶点数组（ver[]存储 A-I）、邻接矩阵（arc[][]存储边的权值）、顶点数和边数。create_graph函数初始化了图：

• 顶点 A-I 对应下标 0-8；
• 邻接矩阵中，arc[i][j]是顶点 i 和 j 之间的权值，自身（i=j）权值为 0，不直接相连的顶点权值设为极大值（Max=0x7fffffff）；
• 无向边双向赋值（比如 A-B 的权值 10，既存arc[0][1]也存arc[1][0]），保证图的对称性。

2. Prim 算法的核心步骤（对应prim函数）

算法从 A 点（下标 0）开始，用两个数组辅助：

• weight[]：存储 “当前已连通区域到每个未连通顶点” 的最短权值；
• ver_index[]：存储 “最短边的起点”（比如ver_index[j]=k，表示从顶点 k 到 j 的边是当前最短）。

第一步：初始化

• 从 A 点（下标 0）出发，所以weight[0]=0（已连通，权值设为 0 标记），ver_index[0]=0（起点是自己）；
• 其他顶点的weight[i]初始化为 A 点到该顶点的权值（比如weight[1]=arc[0][1]=10，即 A 到 B 的权值），ver_index[i]=0（起点都是 A）。

第二步：循环选最短边（共选 8 条，因为 n 个顶点的生成树有 n-1 条边）

1. 找weight[]中最小的非 0 值（非 0 表示未连通），记为min，对应的顶点下标为k（这是本次要纳入连通区域的顶点）；
2. 输出这条最短边：起点是ver[ver_index[k]]（比如 k=1 时，ver_index[1]=0，起点是 A），终点是ver[k]（B），权值是min（10）；
3. 把weight[k]设为 0，标记该顶点已连通；
4. 更新weight[]：用新纳入的顶点 k，检查它到所有未连通顶点的权值，如果比当前weight[j]小，就更新weight[j]和ver_index[j]（比如 k=8 是 I 点，I 到 C 的权值 8 比之前 A 到 C 的极大值小，就把weight[2]更新为 8，ver_index[2]=8）。

举个实际运行例子：

• 第一次循环：找到weight[1]=10（A-B），输出 (A,B) 权值 10，B 纳入连通区域；
• 第二次循环：更新后weight[]中最小的是weight[8]=12（A-I），输出 (A,I) 权值 12，I 纳入；
• 第三次循环：I 到 C 的权值 8 最小，输出 (I,C) 权值 8，C 纳入；
• 以此类推，直到所有 9 个顶点都连通，最终输出 8 条边，总权值最小。

三、Prim 算法的特点：简单好懂，适合稠密图

• 优点：逻辑直观，就像 “画圈圈” 一样，逐步把顶点纳入连通区域，代码实现也不复杂（两层循环 + 邻接矩阵）；
• 适用场景：稠密图（顶点少、边多），因为时间复杂度主要和顶点数有关（O (n²)），和边数无关，稠密图中效率更高；
• 关键提醒：生成树的总权值是固定的，但可能有多个不同的生成树（只要总权值最小），具体取决于每次选最短边时的取舍（如果有多个相同最小权值）。

四、运行代码看结果

编译运行代码后，会依次输出 8 条最短边，比如：

(A,B)权值是：10

(A,I)权值是：12

(I,C)权值是：8

(C,D)权值是：22

(D,H)权值是：16

(H,E)权值是：7

(A,F)权值是：11

(F,G)权值是：17

把这些边的权值相加，就是最小总造价，所有顶点 A-I 都连通，没有环路 —— 这就是 Prim 算法的最终成果！