Prim 与 Kruskal：两条通往最小生成树的路径

Prim 与 Kruskal：两条通往最小生成树的路径

在图论的世界里，最小生成树一直是一个绕不开的话题。从数据压缩，到网络布线，再到图像处理，几乎所有与图结构相关的工程系统都要用到它。为求得一棵最小生成树，Prim 和 Kruskal 算法可谓是最常见的两套方案。两者目标一致，却从不同方向切入，构造方式迥异，各自发挥着独特的优势。

为了更好地理解这两者的差异，不妨换一种叙述方式，把它们想象成“从点出发”与“从边出发”的两位选手，各自遵循着完全不同的建树逻辑。

一、两条思路：从点长大 vs. 从边挑选

Prim 算法的思路更像是在图中“生长”一棵树。起点任选一个，然后不断挑选能与当前树连接的最小权值边，逐步吸收新的顶点。随着顶点数量增加，这棵树最终覆盖了整张图。

Kruskal 的方式则完全不同。它不关心从哪个点开始，而是把所有边按权值排序，再从最小的边依次筛选，只要加入后不会形成环，就顺理成章地纳入生成树。最终，当挑选了足够多的边（V-1 条）时，最小生成树也就自然拼装完成。

若将 Prim 比喻为“长树”，那么 Kruskal 更像是“拼树”。

二、适用场景：稠密图与稀疏图的分界线

Prim 更适合处理稠密图。原因很简单：在边非常多的情况下，邻接矩阵或邻接表能让 Prim 更高效地找到与当前树相连的最小边，配合优先队列还能进一步降低复杂度。

Kruskal 则天生适合稀疏图。边少意味着边排序的成本不高，而依靠并查集判断是否成环的方式也十分高效。

一句话总结：
稠密图常用 Prim，稀疏图更青睐 Kruskal。

三、时间复杂度：结构设计决定效率

Prim：

• 采用邻接矩阵实现时代价为 O(V²)。

• 若使用邻接表并结合优先队列，则可优化至 O(E log V)。

Kruskal：

• 边排序是主要成本，为 O(E log E)，在数学上近似于 O(E log V)。

• 并查集几乎可以视为 O(1) 操作。

两者没有绝对的优劣，更多是结构组织方式带来的自然差异。

四、核心判断：Prim 不怕环，Kruskal 必须防环

Prim 不会在意环的问题。因为整棵树始终从一个连通结构生长，没有分裂，因此天然避免了形成回路。

Kruskal 则必须小心处理环的问题。毕竟它是从全局边列表一条条筛选，稍不注意便可能让某条边连接已经相连的两个顶点。为了避免这种情况，引入了并查集，用于判断某条边是否会生成环。

这也是两者数据结构最明显的区分点之一。

五、小结：同一目标，不同路径

Prim 是从局部向外扩散；
Kruskal 是从整体中逐条挑选。

Prim 强调从一个点不断“长大”；
Kruskal 更注重边的全局排序与选择。

在实际项目中，如何选择往往取决于数据：图的顶点数量、边的密度、数据输入的结构形式、以及是否便于维护并查集或优先队列。

但无论选哪一种，得到的结果都是一致的：
一棵具有最小总权值、连通且无环的生成树。