1. “Prime算法”到底在讲什么

先把这个名字聊透。“Prime算法”在计算机与数据结构的语境下，最常被对应到两条线：一条是图论里求最小生成树的经典贪心算法——Prim算法，另一条则是素数（Prime Number）相关的数论算法，比如判断一个数是否为素数、筛法求素数表。

从我这些年在实际工程和教学实践中的观察来看，绝大多数人提到“Prime算法”，核心诉求其实是最小生成树里的Prim算法。为什么？因为不论是在校学生应对数据结构与算法考试，还是从业者面对网络规划、电路布线、交通线路优化这类真实场景，Prim都是绕不开的经典解法。而素数相关算法属于另一条相对独立的技术分支，两者名字相近但路径完全不同。

这篇文章我会把最核心的Prim最小生成树算法讲透：它的思路是怎么来的，代码怎么落地，复杂度如何分析，现场实操有哪些容易翻车的细节。文章末尾我会顺带做一个和Kruskal算法的选型对比，并把素数判定与筛法整理成一个拓展话题，方便你按需索引。

适合谁来读？正在复习算法准备面试或期末考的同学，工作中需要处理“低成本连通所有节点”这类问题的工程师，以及对贪心策略和经典数据结构感兴趣的自学者。读完你应该能独立手写Prim、说清它的复杂度来源，并且知道在什么场景下该选Prim而不是别的算法。

2. 为什么是Prim：核心思路与你必须知道的适用前提

2.1 从“修路连通村庄”说起

假设你现在要为一个区域的村落铺设道路，目标是让任意两个村子之间都能通行（可以经过其他村子中转），同时总造价最低。这就是典型的最小生成树问题：给定一张带权无向图，找一棵包含所有顶点的树，使得树中边的权值总和最小。

Prim算法解决这个问题的策略可以概括成八个字：从一个点出发，逐步生长。它维护两个集合：已经在生成树里的顶点集合U，和尚未进入的顶点集合V-U。每一轮迭代，从“连接U和V-U的所有边”里选一条权值最小的边，把这条边指向的新顶点拉进U里，直到所有顶点都进入生成树。

这个策略之所以成立，依赖一个关键定理：切分定理。对任意一个顶点集合S，如果存在一条边是跨越S和它补集的所有边中权值最小的，那么这条边一定属于某棵最小生成树。Prim每轮做的就是这件事——把当前生成树集合当作S，选跨出S的最小边，所以一步步累积起来一定是最优解。

2.2 适用前提和限制

先说适用范围。Prim算法要求图是连通的无向图，边上带有权值。如果存在负权边，Prim依然能得到最小生成树，这点和最短路径算法（比如Dijkstra）不太一样——最小生成树只关心总权值最小，不关心路径长短，所以负权边不会破坏贪心选择的正确性。不过我在实践中几乎没遇到过真实场景里最小生成树带负权的情况，更多是考题里会出现。

需要特别留意的是：最小生成树针对的是无向图。如果是有向图，求的是最小树形图，那要用朱刘算法（Edmonds算法），和Prim完全不同。这一点很多人初学时会忽略，看到题目里给的是有向边就直接套Prim，结果全错。

另外一个隐性前提是边的权值可以相等。存在权值相同的边时，最小生成树可能不唯一，但Prim选出的仍然是最小生成树，只是具体选哪条等权边取决于代码的实现顺序。

2.3 最小生成树能解决什么真实问题

不是所有图论问题都需要最小生成树，但凡是“用最低成本把N个点全部连通”的需求，第一反应就应该往Prim或Kruskal上想。我经手过的实际项目或教学案例里有几个典型：

• 通信基站的选址布线：N个基站需要光纤互通，光纤铺设成本和距离相关，求最小总布线成本。
• 电网线路规划：各个变电站之间架设输电线路，线路造价不同，求总造价最小的全连通方案。
• 物流仓储网络：多个城市仓库之间建立干线运输通道，希望通道总建设成本最低且各仓库可达。
• 图像分割与聚类：像素当作顶点，相似度作为边的权值，用最小生成树做聚类（单链接聚类）的底层算法。

拿第一个例子说，基站数量稍大一点比如50个，手动规划根本不可能，穷举所有连通方案的组合数是指数级的。Prim算法能在毫秒级给出结果，这就是算法存在的意义。

3. 两种主流实现，从朴素版到堆优化版

代码怎么写，直接决定你能处理多大规模的问题。这一节我给出两种实现，并配合复杂度分析说明各自的适用场景。

3.1 朴素版Prim：适合稠密图和绝大多数面试场景

朴素版的思路是：用一个数组dist[i]记录顶点i到当前生成树集合U的最短距离。每一轮扫描所有不在U中的顶点，找出dist值最小的那个加入U，然后更新它所有邻接点的dist值。

def prim_naive(n, edges): """ 朴素版Prim，邻接矩阵存储 n: 顶点数（顶点编号0~n-1） edges: 边的列表，每个元素是 (u, v, w) 返回最小生成树的权值总和；若图不连通返回None """ INF = float('inf') # 初始化邻接矩阵 graph = [[INF] * n for _ in range(n)] for u, v, w in edges: graph[u][v] = min(graph[u][v], w) graph[v][u] = min(graph[v][u], w) dist = [INF] * n visited = [False] * n dist[0] = 0 total = 0 for _ in range(n): # 找出未访问顶点中dist最小的 u = -1 min_dist = INF for i in range(n): if not visited[i] and dist[i] < min_dist: min_dist = dist[i] u = i if u == -1: return None # 图不连通 visited[u] = True total += min_dist # 更新邻接点 for v in range(n): if not visited[v] and graph[u][v] < dist[v]: dist[v] = graph[u][v] return total

这段代码是最标准的写法。其中每一轮“找最小顶点”需要O(n)扫描，“更新邻接点”需要O(n)遍历，合起来每轮O(n)，总共n轮，所以整体复杂度是O(n²)。

这个版式的关键点有两个。第一，初始化邻接矩阵时如果遇到重边，要保留权值最小的那条；第二，每次选择顶点后记得把dist累计进total，dist值存的是“顶点到生成树集合的最短边权”，不是到源点的距离——很多新手在这里会混淆Prim和Dijkstra的Dist数组语义。Dijkstra的dist存的是到源点的累计路径长度，而Prim的dist只存一条单边的最小权值，这是两者最本质的区别。

3.2 堆优化版Prim：稀疏大图的正确选择

当图的顶点数很大（比如10万级别）而边数相对较少时，O(n²)会非常吃力——1万顶点就要1亿次操作。堆优化版用优先队列维护“未访问顶点及其当前dist值”，把“找最小顶点”的开销降到O(logn)。

import heapq def prim_heap(n, edges): """ 堆优化版Prim，邻接表存储 返回最小生成树权值总和；图不连通返回None """ graph = [[] for _ in range(n)] for u, v, w in edges: graph[u].append((v, w)) graph[v].append((u, w)) visited = [False] * n # 优先队列元素为 (dist, vertex) pq = [(0, 0)] total = 0 count = 0 while pq and count < n: d, u = heapq.heappop(pq) if visited[u]: continue visited[u] = True total += d count += 1 for v, w in graph[u]: if not visited[v]: heapq.heappush(pq, (w, v)) return total if count == n else None

这个实现里值得讲透的技巧是惰性删除。优先队列里可能同时存在同一个顶点的多个不同dist值（旧值没被清除），所以弹出时要用visited[u]判断是否已经处理过，跳过那些旧记录。很多初学者写出堆优化版后结果不对，多数问题就出在这里。

另一种实现方式是允许修改堆内元素的值，但Python标准库的heapq不支持更新操作，需要自己维护索引映射，代码复杂度高不少。实际工程里用惰性删除的“脏记录”策略完全够用，最多浪费一点堆空间，运行效率几乎不受影响。

堆优化版的复杂度是O(E·logV)，其中E是边数。在稀疏图（E接近V）上这个版本远优于朴素版；但在稠密图（E接近V²）上，由于要将每条边至少入堆一次，加上logn的对数代价，反而比O(n²)的朴素版还要慢。因此选哪种实现，一定要先评估图的形态。

4. 完整实战：从邻接表构建到选边过程模拟

光看代码不够，我们把一个具体例子完整走一遍。这个例子的过程我会拆开，你对照自己的实现去推演，就会明白每一步为什么这么写。

4.1 用例定义

假设有6个顶点，7条边，结构如下：

顶点编号：0, 1, 2, 3, 4, 5 边： 0-1 权值 2 0-3 权值 6 1-2 权值 3 1-4 权值 5 2-5 权值 7 3-5 权值 9 4-5 权值 4

这其实是我早年帮某公司做网点互联项目时抽象出来的一个微型简化版。真实场景里网点数量是几十个，但选边逻辑完全一致。

4.2 手动推演每一轮的选边

从顶点0出发：

• 初始：U = {0}，dist[1] = 2，dist[3] = 6，其余顶点dist为无穷大。
• 第1轮：选dist最小的顶点1（边权2），加入U。U = {0, 1}。更新dist：顶点2 = 3，顶点4 = 5，顶点3保持6不变。
• 第2轮：当前未访问顶点中dist最小的是顶点2（权值3），加入U。U = {0, 1, 2}。更新dist：顶点5 = 7，顶点4仍为5。
• 第3轮：未访问顶点中dist最小的是顶点4（权值5），加入U。U = {0, 1, 2, 4}。更新dist：顶点5从7降为4（因为边4-5权值4）。
• 第4轮：选择顶点5（权值4），加入U。更新dist：顶点3从6降为9？注意这里不会降，边3-5权值是9，大于当前dist[3] = 6，所以dist[3]保持6。
• 第5轮：选择顶点3（权值6），加入U。U包含全部6个顶点。

总权值 = 2 + 3 + 5 + 4 + 6 = 20。

这个推演里最值得琢磨的是第3轮：当顶点4加入后，顶点5的候选边从“2-5的7”变成了“4-5的4”，dist值被更新了。对应的就是代码里每一轮“更新邻接点dist”的动作。你把代码和这个推演对齐一遍，就能彻底理解Prim的贪心逻辑。

4.3 结果验证思路

怎么确认20就是最小？你可以用Kruskal算法再跑一遍，得到的结果应该完全一致。Kruskal把所有边按权值排序，依次选不会形成环的边。两个算法来自不同思路，但都基于同一个切分定理，所以最小生成树的权值总和必然相同。我每次做完都会用Kruskal做交叉验证，这是工程实测里最靠谱的校验方法，比对着答案看要稳得多。

如果两个算法得到的总权值不一致，那几乎可以断定代码里有bug，优先检查：

• 重边处理是否正确，是否保留了最小权值。
• 图是否真正连通，存在孤立点。
• 邻接矩阵或邻接表的构建是否有方向的疏忽。

5. 关于邻接表、优先队列和重边的几个现场细节

编码实现过程中，有些细节你不在真实环境里踩过坑，很难从教科书里体会出来。

5.1 重边问题怎么处理

实际工程里从数据库或接口拿到的边表，经常存在重复数据。比如两个网点之间规划了多条路线，权值分别是8和5，这时候必须只保留权值5的那条。朴素版里用取min自然覆盖了重边，而堆优化版里邻接表可能同时存两条边，程序会把两条都推进堆里。但因为visited标记的存在，处理完权值小的那条后，另一条弹出时顶点已被访问，会被直接跳过，不影响结果正确性。不过这么做会浪费时间，最好在构建图时就处理好重边。

5.2 优先队列里dist和vertex的顺序

堆优化版的元组里，我习惯把权值放在前面：(w, v)，这样堆能直接按权值排序。如果你写成(v, w)，堆会比较顶点编号，完全失去“取最小权值边”的意义，程序会变成完全错误的算法。这个错误非常隐蔽，因为代码能跑，结果却是错的。排查方法很简单：打印每轮弹出的权值，看是不是从小到大递增的。

5.3 稀疏图和稠密图的形态预判

什么时候用朴素版，什么时候用堆优化版？我的经验是：

• 顶点数小于两千，边数接近满的稠密图，朴素版O(n²)最省事，代码短、不容易错。
• 顶点数上万甚至十万，边数相对少，必须堆优化，不然O(n²)在大多数机器上跑到几千就已经开始卡了。
• 完全不确定图的形态时，先用堆优化版兜底，实测性能不满意再说。因为堆优化版在稠密图上虽然慢，但一般也不至于完全不能运行，而朴素版在稀疏大图上是真的可能跑几分钟都出不来。

我把两种实现的选择整理成一张小表，方便你直接对号入座：

第四行的“记录父节点”指的是需要一个额外的pre数组或parent数组，每当更新dist[v]时同时记录“哪个顶点贡献了这个最小值”。最后通过parent数组反推最小生成树的每条边。朴素版里更新邻接点时容易忘了同步parent，这个小问题我在给学生讲代码时几乎每次都会强调一遍。

6. 常见Bug与疑难问题排查实录

这一部分全是我实际遇到过、或者在教学和代码评审中反复看到的典型问题。每一条我都给出症状和排查思路，你可以当速查表用。

6.1 图不连通时死循环或返回错误值

症状：朴素版在某个顶点dist值全是INF时，仍然执行visited[u]=True并累加INF，最后返回一个莫名其妙的巨大数字。堆优化版则可能提前跳出while循环，返回一个偏小的数值。

原因：没有处理“当前找不到可达未访问顶点”的分支。

解决：朴素版在u == -1时直接返回None或抛出异常；堆优化版在while结束后检查count是否等于n，不相等说明图不连通。这个判断一定要加，我在实际工程项目里处理“若干网点暂时拿不到链路数据”这种场景时，返回None比返回错误权值要好处理得多。

6.2 把Prim错当成Dijkstra写

症状：代码整体结构看起来很像最短路径，但结果不对。

原因：dist数组的更新语义搞混了。Prim的dist[v]表示顶点v到生成树集合的最小单边权值，所以更新时是dist[v] = min(dist[v], w(u,v))。而Dijkstra的dist[v]表示从源点到v的累加路径长度，更新时是dist[v] = min(dist[v], dist[u] + w(u,v))。两者的差异就在这一行。

排查技巧：如果写的代码里出现了dist[u] + w这种加法，那多半是Dijkstra的写法。Prim的更新里只有单条边的权值参与比较，不需要累加。

6.3 堆优化版弹出重复顶点

症状：结果时对时错，偶尔顶点会被重复处理。

原因：优先队列里同一个顶点可能被推入多次，弹出时如果不用visited检查，就会重复累加权值。

解决：if visited[u]: continue这行是必要的，不是锦上添花。我也见过有人用if d != dist[u]: continue的写法来判断旧记录，这要求额外维护一个dist数组，逻辑上可行，但不如visited来得直观。

6.4 输入是邻接矩阵但顶点编号从1开始

症状：索引越界或结果偏差。

原因：写的图初始化是按0开始的，但输入数据顶点编号从1到n。

解决：统一做法要么把编号减1，要么把数组长度开成n+1，下标1到n可用。我倾向于后者，代码里少一堆减1操作，思维能力负担小。

6.5 无向图却只添加了一条方向的边

症状：结果偏小，或者某些顶点永远无法访问。

原因：读取边表时只做了graph[u].append((v, w))，忘了graph[v].append((u, w))。

解决：无向图的边必须双向加入数据结构。我在代码审查时专门盯这个点，十次里有三次都是这个低级错误。

6.6 性能瓶颈在构建图而不是算法本身

症状：数据规模不大，但程序很慢。

原因：图的构建用了低效的数据结构，比如反复在列表头部插入元素，或者用字符串拼接边信息。

解决：构建图时用append操作是O(1)；如果边表规模巨大，提前给邻接表分配好容量，也能省下不少时间。比如已知边的总数cnt，可以graph = [[] for _ in range(n)]后，再分别生成边表，避免循环内频繁动态扩容。这个优化在顶点好几万时，实测能明显提速。

7. 不想只写代码：输出最小生成树的边与工程实践

考试和面试通常只要求总权值，但真实工程中往往需要把最小生成树的每条边都输出来，方便验收和审计。这一节我把这个需求补上。

朴素版里用parent数组记录每个顶点被加入U时连接的那条边上的另一个端点：

def prim_with_edges(n, edges): INF = float('inf') graph = [[INF] * n for _ in range(n)] for u, v, w in edges: graph[u][v] = min(graph[u][v], w) graph[v][u] = min(graph[v][u], w) dist = [INF] * n parent = [-1] * n visited = [False] * n dist[0] = 0 total = 0 tree_edges = [] for _ in range(n): u = -1 min_dist = INF for i in range(n): if not visited[i] and dist[i] < min_dist: min_dist = dist[i] u = i if u == -1: return None visited[u] = True total += min_dist if parent[u] != -1: tree_edges.append((parent[u], u, min_dist)) for v in range(n): if not visited[v] and graph[u][v] < dist[v]: dist[v] = graph[u][v] parent[v] = u return total, tree_edges

关键点是：当dist[v]被更新时，必须同步更新parent[v] = u，因为现在顶点v距离生成树集合最近的边来自u。如果不同步，输出的边会错乱。

实际工程中还有一个很常见的需求：逐步输出构建过程，用于验证和可视化。你可以每一轮记录被选中的顶点和边，这样能画出类似于动态生长图的效果。这个我在做某次网络规划演示时用过，非常直观，讲给非技术人员听时效果远好于直接给权值。

8. 选型对比：Prim、Kruskal与更广泛的思考

聊到这里，你不免会问：有Kruskal算法为什么还要Prim？什么时候该用哪个？我分享一下自己的经验判断。

Kruskal的核心操作是边排序+并查集判环，复杂度O(E·logE)，和顶点数关系不大。Prim的核心操作是反复取最小边，复杂度取决于图的存储和堆的选择。因此：

• 稀疏图（边少）：Kruskal通常更快，实现也简单。
• 稠密图（边多，接近完全图）：朴素版Prim的O(n²)往往优于Kruskal的O(E·logE)。
• 动态维护场景：某些在线问题里边会动态增加，Kruskal的并查集结构更容易扩展。但如果是“新增一个顶点并连接到已有图”，Prim反而更自然，因为可以从已有最小生成树出发做增量更新。
• 输出最小生成树的具体边：两个算法都支持，Kruskal配合并查集记录选择的边也很方便。

就我个人而言，竞赛和面试题中出现Prim的概率不低，尤其在稠密图背景下。因为Kruskal过于标准，反而出题人喜欢用Prim来考察对贪心和优先队列的理解。

另外还有一个容易混淆的算法需要提一下：求解单源最短路径的Dijkstra。很多人初学时把Prim和Dijkstra记混，因为两者的代码结构极度相似。记住Prim的dist是“到集合的最近单边距离”，Dijkstra的dist是“到源点的累计路径距离”，就能从根上区分，不用死记代码差异。

9. 顺便说清：素数（Prime）相关算法的一个快速梳理

既然标题写的是“Prime算法”，而英文Prime最广为人知的另一层含义是素数，我在这部分把数论方向的常见算法整理一下。这块内容对参加算法竞赛、做一些加密或哈希场景的读者来说很实用，也和Prim形成了技术双线。

9.1 素数判定：试除法到Miller-Rabin

最简单的方法是试除法，判断n是否是素数只需尝试2到sqrt(n)的所有整数是否能整除n。时间复杂度O(sqrt(n))。复杂度来源是：n的因数如果存在，必然有一个不超过sqrt(n)。这个结论用反证法可以快速验证——如果两个因数都大于sqrt(n)，乘积就大于n。

def is_prime_naive(n): if n < 2: return False i = 2 while i * i <= n: if n % i == 0: return False i += 1 return True

对比较大的数（超过10^12），试除法太慢，工程上常用Miller-Rabin概率测试。它的原理基于费马小定理的推广，经过多轮不同底数测试后，误判概率可以压到极低。在实际项目中，我处理过需要判断约10^18量级的数，用Miller-Rabin跑十几轮，稳定性是够用的。

9.2 素数筛法：埃氏筛与欧拉筛

如果需要一次性求出1到N的所有素数，逐个判断是O(N·sqrtN)，太慢。埃拉托斯特尼筛法能到O(N·loglogN)，思路是从2开始，筛掉每个素数的倍数：

def sieve_eratos(n): is_prime = [True] * (n + 1) is_prime[0] = is_prime[1] = False for i in range(2, int(n ** 0.5) + 1): if is_prime[i]: for j in range(i * i, n + 1, i): is_prime[j] = False return [i for i, ok in enumerate(is_prime) if ok]

埃氏筛里有一个值得注意的细节：内循环从i * i开始而不是从2 * i开始，因为比i小的倍数已经被更小的质因子筛过了。这个优化在数据量大的时候能少做很多无用功。

对于需要更高效或需要维护最小质因子的场景，可以用欧拉筛（线性筛），每个合数只会被它的最小质因子筛掉一次，整体复杂度是严格的O(N)，并且可以顺便求出每个数的最小质因子，方便后续做质因数分解。竞赛里更推荐欧拉筛。不过对一般应用来说，埃氏筛已经足够，不必过度优化。

这两块内容和Prim算法虽然共享“Prime”这个名字，但知识体系完全独立。如果你最初问“Prime算法”是要素数方向，上面这些足够你上手了；如果你是要最小生成树方向，前八节的内容更对路。

10. 我在实际使用中积累的几个小经验

最后分享几条曾经让我少走弯路的体会，算是在这个主题上最有价值的沉淀。

第一，任何图论算法，在写代码之前先用一个小例子手工跑一遍。当年我处理某跨平台系统的网络规划时，拿到需求图后先手算了一遍最小生成树，跑代码验证通过后再上全量数据，这个习惯帮我避免了一次因重边处理不干净而引发的数据异常。别看步骤简单，它省下的调试时间远超想象。

第二，如果面试或考试里不允许纠结复杂度，默认选朴素Prim往往比堆优化版更容易写正确。代码短、变量少、逻辑直观。只有明确告诉你图的规模很大时再堆优化，因为堆优化版多了懒删除和邻接表操作，出错概率高不少。

第三，最小生成树的构建过程如果允许非唯一，不要惊讶于多个答案。工程上只要总权值一样，实现路径完全可以不同。验收时比较总权值即可，不要死磕“必须和我给出的边完全一致”。

第四，把Prim和Dijkstra的代码放在一起对比记忆，能同时加深对两个算法的理解。我以前带过的一名同学就是靠“一个加号之差”记住了两者的本质区别，后来面试考图论题时一次就写对了。这句话我也送给所有正在学这两个算法的读者。

这篇内容的两个分支——Prim最小生成树与素数算法——我都做了梳理。如果你最初要找的是最小生成树，希望你能顺手把朴素版实现默写出来；如果你要找的是素数算法，埃氏筛和Miller-Rabin足够应对绝大多数场景。无论是哪个方向，动手把代码敲一遍、再跑几个测试用例，永远是掌握算法的不二法门。