AI summary
type
status
date
slug
summary
category
tags
icon
password
最小生成树算法主要有 Prim 算法和 Kruskal 算法两种，这两种算法虽然都运用了贪心思想，但从实现上来说差异还是蛮大的。

Kruskal 算法

Kruskal 算法其实很容易理解和记忆，其关键是要熟悉并查集算法，如果不熟悉，建议先看下前文 Union-Find 并查集算法。
接下来，我们从最小生成树的定义说起。

最小生成树

先说「树」和「图」的根本区别：树不会包含环，图可以包含环。
如果一幅图没有环，完全可以拉伸成一棵树的模样。说的专业一点，树就是「无环连通图」。
那么什么是图的「生成树」呢，其实按字面意思也好理解，就是在图中找一棵包含图中的所有节点的树。专业点说，生成树是含有图中所有顶点的「无环连通子图」。
容易想到，一幅图可以有很多不同的生成树，比如下面这幅图，红色的边就组成了两棵不同的生成树：
notion image
对于加权图，每条边都有权重，所以每棵生成树都有一个权重和。比如上图，右侧生成树的权重和显然比左侧生成树的权重和要小。
那么最小生成树很好理解了，所有可能的生成树中，权重和最小的那棵生成树就叫「最小生成树」。
一般来说，我们都是在无向加权图中计算最小生成树的，所以使用最小生成树算法的现实场景中，图的边权重一般代表成本、距离这样的标量。
Kruskal 算法的一个难点是保证生成树的合法性，因为在构造生成树的过程中，你首先得保证生成的那玩意是棵树（不包含环）对吧，那么 Union-Find 算法就是帮你干这个事儿的。怎么做到的呢？

261. 以图判树

给你输入编号从 0 到 n - 1 的 n 个结点，和一个无向边列表 edges（每条边用节点二元组表示），请你判断输入的这些边组成的结构是否是一棵树。
对于添加的这条边，如果该边的两个节点本来就在同一连通分量里，那么添加这条边会产生环；反之，如果该边的两个节点不在同一连通分量里，则添加这条边不会产生环。
而判断两个节点是否连通（是否在同一个连通分量中）就是 Union-Find 算法的拿手绝活，所以这道题的解法代码如下：
如果你能够看懂这道题的解法思路，那么掌握 Kruskal 算法就很简单了。
所谓最小生成树，就是图中若干边的集合（我们后文称这个集合为 mst，最小生成树的英文缩写），你要保证这些边：
  1. 包含图中的所有节点。
  1. 形成的结构是树结构（即不存在环）。
  1. 权重和最小。
有之前题目的铺垫，前两条其实可以很容易地利用 Union-Find 算法做到，关键在于第 3 点，如何保证得到的这棵生成树是权重和最小的。
这里就用到了贪心思路：
将所有边按照权重从小到大排序，从权重最小的边开始遍历，如果这条边和 mst 中的其它边不会形成环，则这条边是最小生成树的一部分，将它加入 mst 集合；否则，这条边不是最小生成树的一部分，不要把它加入 mst 集合。
这样，最后 mst 集合中的边就形成了最小生成树，下面我们看两道例题来运用一下 Kruskal 算法。

1135. 最低成本连通所有城市

给你输入数组 conections，其中 connections[i] = [xi, yi, costi] 表示将城市 xi 和城市 yi 连接所要的costi（连接是双向的），请你计算连接所有城市的最小成本。
这是一道标准的最小生成树问题，每座城市相当于图中的节点，连通城市的成本相当于边的权重，连通所有城市的最小成本即是最小生成树的权重之和。
notion image
刷着刷着系统维护了，哈哈，第一次见。

1584. 连接所有点的最小费用

给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。
连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。
请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。
很显然这也是一个标准的最小生成树问题：每个点就是无向加权图中的节点，边的权重就是曼哈顿距离，连接所有点的最小费用就是最小生成树的权重和。
所以解法思路就是先生成所有的边以及权重，然后对这些边执行 Kruskal 算法即可：
  • sort() 是 Python 列表的原地排序方法，会直接修改 edges。
  • key=lambda x: x[2] 表示 按照每条边的第三个元素（即权重 w）进行排序。
这道题做了一个小的变通：每个坐标点是一个二元组，那么按理说应该用五元组 (x_i, y_i, x_j, y_j, weight) 表示一条带权重的边，但这样的话不便执行 Union-Find 算法；所以我们用 points 数组中的索引代表每个坐标点，这样就可以直接复用之前的 Kruskal 算法逻辑了。

复杂度分析

通过以上三道算法题，相信你已经掌握了 Kruskal 算法，主要的难点是利用 Union-Find 并查集算法向最小生成树中添加边，配合排序的贪心思路，从而得到一棵权重之和最小的生成树。
最后说下 Kruskal 算法的复杂度分析：
假设一幅图的节点个数为 V，边的条数为 E，首先需要 O(E) 的空间装所有边，而且 Union-Find 算法也需要 O(V) 的空间，所以 Kruskal 算法总的空间复杂度就是 O(V+E)。
时间复杂度主要耗费在排序，需要 O(ElogE) 的时间，Union-Find 算法所有操作的复杂度都是 O(1)，套一个 for 循环也不过是 O(E)，所以总的时间复杂度为 O(ElogE)。

Prim 算法

首先，Prim 算法也使用贪心思想来让生成树的权重尽可能小，也就是「切分定理」，这个后文会详细解释。
其次，Prim 算法使用 BFS 算法思想 和 visited 布尔数组避免成环，来保证选出来的边最终形成的一定是一棵树。
Prim 算法不需要事先对所有边排序，而是利用优先级队列动态实现排序的效果，所以我觉得 Prim 算法类似于 Kruskal 的动态过程。
下面介绍一下 Prim 算法的核心原理：切分定理。

切分定理

「切分」这个术语其实很好理解，就是将一幅图分为两个不重叠且非空的节点集合：
notion image
红色的这一刀把图中的节点分成了两个集合，就是一种「切分」，其中被红线切中的的边（标记为蓝色）叫做「横切边」。
当然，一幅图肯定可以有若干种切分，因为根据切分的定义，只要你能一刀把节点分成两部分就行。接下来我们引入「切分定理」。
对于任意一种「切分」，其中权重最小的那条「横切边」一定是构成最小生成树的一条边。
关于切分定理，可以用反证法证明：
首先证明存在性，给定一幅图的最小生成树，那么随便给一种「切分」，一定至少有一条「横切边」属于最小生成树。因为最小生成树要包含所有节点，一个切分会把节点切成两个集合，那么一定有一条边跨越这两个集合，否则你这个最小生成树就是有问题的。
其次证明，一个「切分」中权重最小的那条「横切边」一定属于最小生成树。如果不是的话，说明你这个最小生成树的权重和不是最小的，与最小生成树的定义矛盾。
有了这个切分定理，你大概就有了一个计算最小生成树的算法思路了：
既然每一次「切分」一定可以找到最小生成树中的一条边，那我就随便切呗，每次都把权重最小的「横切边」拿出来加入最小生成树，直到把构成最小生成树的所有边都切出来为止。
嗯，可以说这就是 Prim 算法的核心思路，不过具体实现起来，还是要有些技巧的。
因为你没办法让计算机理解什么叫「随便切」，所以应该设计机械化的规则和章法来调教你的算法，并尽量减少无用功。
我们思考算法问题时，如果问题的一般情况不好解决，可以从比较简单的特殊情况入手，Prim 算法就是使用的这种思路。
按照「切分」的定义，只要把图中的节点切成两个不重叠且非空的节点集合即可算作一个合法的「切分」，那么我只切出来一个节点，是不是也算是一个合法的「切分」？
是的，这是最简单的「切分」，而且「横切边」也很好确定，就是这个节点的边。
notion image
既然这是一个合法的「切分」，那么按照切分定理，这些「横切边」AB, AF 中权重最小的边一定是最小生成树中的一条边。
好，现在已经找到最小生成树的第一条边（边 AB），然后呢，如何安排下一次「切分」？
按照 Prim 算法的逻辑，我们接下来可以围绕 A 和 B 这两个节点做切分：
notion image
然后又可以从这个切分产生的横切边（图中蓝色的边）中找出权重最小的一条边，也就又找到了最小生成树中的第二条边 BC …
Prim 算法的逻辑就是这样，每次切分都能找到最小生成树的一条边，然后又可以进行新一轮切分，直到找到最小生成树的所有边为止。
这样设计算法有一个好处，就是比较容易确定每次新的「切分」所产生的「横切边」。
比如回顾刚才的图，当我知道了节点 A, B 的所有「横切边」（不妨表示为 cut({A, B})），也就是图中蓝色的边，是否可以快速算出 cut({A, B, C})，也就是节点 A, B, C 的所有「横切边」有哪些？
是可以的，因为我们发现：cut({A, B, C}) = cut({A, B}) + cut({C}) ，而 cut({C}) 就是节点 C 的所有邻边。
在进行切分的过程中，我们只要不断把新节点的邻边加入横切边集合，就可以得到新的切分的所有横切边。
当然，细心的读者肯定发现了，cut({A, B}) 的横切边和 cut({C}) 的横切边中 BC 边重复了。
不过这很好处理，用一个布尔数组 inMST 辅助，防止重复计算横切边就行了。
最后一个问题，我们求横切边的目的是找权重最小的横切边，怎么做到呢？
很简单，用一个 优先级队列 存储这些横切边，就可以动态计算权重最小的横切边了。
完整代码如下：

复杂度分析

这里我们可以再回顾一下本文开头说的 Prim 算法和 Kruskal 算法 的联系：
Kruskal 算法是在一开始的时候就把所有的边排序，然后从权重最小的边开始挑选属于最小生成树的边，组建最小生成树。
Prim 算法是从一个起点的切分（一组横切边）开始执行类似 BFS 算法的逻辑，借助切分定理和优先级队列动态排序的特性，从这个起点「生长」出一棵最小生成树。
说到这里，Prim 算法的时间复杂度是多少呢？
这个不难分析，复杂度主要在优先级队列 pq 的操作上，由于 pq 里面装的是图中的「边」，假设一幅图边的条数为 E，那么最多操作 O(E) 次 pq。每次操作优先级队列的时间复杂度取决于队列中的元素个数，取最坏情况就是 O(logE)。
所以这种 Prim 算法实现的总时间复杂度是 O(ElogE)。回想一下 Kruskal 算法，它的时间复杂度主要是给所有边按照权重排序，也是 O(ElogE)。
不过话说回来，和后文 Dijkstra 算法 类似，Prim 算法的时间复杂度也是可以优化的，但优化点在于优先级队列的实现上，和 Prim 算法本身的算法思想关系不大，所以我们这里就不做讨论了，有兴趣的读者可以自行搜索。
接下来，可以把之前用 Kruskal 算法解决的力扣题目运用 Prim 算法再解决一遍。这里略了。

其他理解

对于 Prim 算法的理解，用教科书上的“加点”可以更好接受。
设已被连入最小生成树的集合位 MST，则每一次选取连接到 MST 中 cost 最小的点。因此优先队列里永远放的都是点和该点连接到 MST 需要的最小 cost（其实也还是边的权值），然后随着算法的执行，每个点连接到 MST 的 cost 也会不断被更新（不断往优先级队列里插入更小的 cost，原来的 cost 不会被删除）。
这样想可以把 Prim 和 Dijkstra 完全类比。
1135. 最低成本连通所有城市 更简洁的代码如下：