LeetCode 解题报告(684,685,721)-并查集介绍及应用 | 吴良超的学习笔记

LeetCode 解题报告(684,685,721)-并查集介绍及应用 | 吴良超的学习笔记

有两个经典的算法可用来解决 最小生成树 问题： Kruskal 算法 和 Prim 算法。其中 Kruskal 算法中便应用了并查集这种数据结构，该算法的步骤如下

1. 新建图G，G中拥有原图中相同的节点，但没有边
2. 将原图中所有的边按权值从小到大排序
3. 从权值最小的边开始，如果这条边连接的两个节点于图G中不在同一个连通分量中，则添加这条边到图G中
4. 重复3，直至图G中所有的节点都在同一个连通分量中

该算法的动图显示如下(摘自维基百科)

Kruskal 算法很简单，实际上 Kruskal 算法是一种贪心算法，并且已被证明最终能够收敛到最好结果。而在实现 Kruskal 算法时，则需要用到并查集这种数据结构来减小算法的时间复杂度。下面将详细介绍这种数据结构。

在介绍并查集前，顺便介绍一下 Prime 算法，Prime 算法也是一种贪心算法，而且也被证明了最终能够得到最好的结果，只是两者的侧重点不同， Kruskal 算法维护的是一个边的集合，而 Prime 算法则同时维护了一个边的集合和一个点的集合，Prim 算法的过程如下

1. 输入：一个加权连通图，其中顶点集合为V，边集合为E；
2. 初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {}；
3. 重复下列操作，直到Vnew = V：
   1. 在集合E中选取权值最小的边（u, v），其中u为集合 Vnew 中的元素，而v则是V中没有加入Vnew的顶点（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
   2. 将v加入集合Vnew中，将（u, v）加入集合Enew中；
4. 输出：使用集合Vnew和Enew来描述所得到的最小生成树。

Read full article from LeetCode 解题报告(684,685,721)-并查集介绍及应用 | 吴良超的学习笔记