并查集的学习与总结

前言

前两天在刷LeetCode每日一题的时候连续遇到了两天有并查集标签的题目，从来没有学过这个算法的我只能硬着头皮去看题，看评论区和题解区大家用并查集都很容易的解决了题目，群里也在讨论一些类似于并查集的优化呀什么的，而我都不知道这是个什么。于是下定决心要学一下这个“神秘的并查集”。

查找资料

在群里问了一些大佬，怎么学并查集，有人推荐《算法4》这本书，说这本书的开头就是并查集，在coursera上也有公开课，coursera还可以判题。我在网上找到了《算法4》的pdf版，在pdf版中，第一章的第五部分：1.5案例研究：union-ﬁnd算法，讲了并查集的相关知识。
另外群主负雪明烛发了一个《2013年王道论坛计算机考研机试指南》，在这里面，第五章图论的第二部分，也讲到了并查集。
群里的liweiwei大佬的个人刷题笔记gitbooks网站上的第5章-高级数据结构中，也有并查集的总结，大佬给了一个思维导图，让人很好理解。liweiwei的网站。
当然，少不了91算法群主lucifer大佬的个人博客上的总结，群主还给出了两个python的并查集模板，一个是基础版本，一个是优化版本，可以在理解了的基础上，熟练背诵，作为以后刷题的一个板子。
在91算法群主博客的推荐中，给了另一个大佬的leetcode并查集题解链接，发现这是另外一个大佬labuladong的总结（labuladong的公众号老早就关注了），以及在labuladong的算法小抄（修订）.pdf中的第四章高频面试系列中，讲到了union-ﬁnd的详解及其应用。

不怕大佬没总结，就怕大佬总结了你不看。这么多的资料足够掌握“小小并查集”了

学习

labuladong的表述中说到：Union-Find 算法，也就是常说的并查集算法，主要是解决图论中「动态连通性」问题的。

所谓并查集，一个并：Union，一个查：Find，还有一个判断节点是否是同一个根节点（同类）的：connected。

在union中，会将两棵树合到一起，使他们的根节点root相同。平衡性优化是在union函数中实现的，即在类中加入一个size列表[]或者字典{}用来计算某一棵树的重量，即这棵树有多少个节点，比如说size[3] = 5表示，以节点3为根的那棵树，总共有5个节点。最后用一个if语句来判断，将重量小的树加到重量大的树上。在liweiwei的总结中，这种方法叫做基于size的优化方法，其实还有一种叫做基于rank的优化方法，即根据节点的深度来当作if的判定条件。
在find中，会判断某个节点属于哪颗树（即哪一类），即它的根节点root是谁。路径压缩是在find函数中是实现的，在这里，我们掌握普通的压缩就可以了，只需要一行代码self.parent[x] = self.parent[self.parent[x]]即可实现树的压缩，而且压缩之后树的深度最多只有3（包括根节点），这种方法通常称之为隔代压缩（基于循环）。在liweiwei的总结中，详细说明了另外一种压缩：完全压缩（基于递归），这个就偏难理解一点，每轮递归的返回值都是parent[x]，这种压缩方式压缩树之后可以将树的深度压缩到只有2，即所有节点的父节点都是根节点，正常情况下需要用到完全压缩很少，掌握隔代压缩就行了。可能很多人都会注意到这一点：路径压缩后，还需要平衡性优化吗？，这个问题，liweiwei和labuladong都谈到了他们的理解。

liweiwei：我们发现在路径压缩的过程中，我们之前引入的辅助合并的数组，不管是 rank 还是 size，它们的定义都不准确了，因为我们在路径压缩的过程中没有对它们的定义进行维护。其实写到这里，数组 rank 还是数组 size 都不太重要了，我们只用在 find 的时候，做好路径压缩，把孩子结点指向父亲结点即可。

labuladong：也就是说，去掉重量平衡，虽然对于单个的 find 函数调用，时间复杂度依然是 O(1)，但是对于 API 调用的整个过程，效率会有一定的下降。当然，好处就是减少了一些空间，不过对于 Big O 表示法来说，时空复杂度都没变。

所以我的结论是，在路径压缩后，用平衡性优化也行，不用也行，只有很微小的空间和时间的差距，不影响大局。在实际操作过程中可视题目具体的时间和空间的要求加或者不加平衡性优化。

总结

以上就是我对并查集的学习和总结。实际操作还需要再题目中去训练。
我只看了labuladong、liweiwei、lucifer三位的总结，其中labuladong总结的更基础，让人容易理解和入门这个并查集的概念，而liweiwei总结的更加全面和深刻，在并查集的优化和压缩上讲的更细，至于代码，学习lucifer给的两个Python模板就足够了。另外好像大家都说是《算法4》这本书讲的并查集最全面最好，但是现在我已经会了。

附代码(lucifer)

这是一个我经常使用的模板，我会根据具体题目做细小的变化，但是大体是不变的。

class UF:
    parent = {}
    cnt = 0
    def __init__(self, M):
        # 初始化 parent 和 cnt

    def find(self, x):
        while x != self.parent[x]:
            x = self.parent[x]
        return x
    def union(self, p, q):
        if self.connected(p, q): return
        self.parent[self.find(p)] = self.find(q)
        self.cnt -= 1
    def connected(self, p, q):
        return self.find(p) == self.find(q)

如果你想要更好的性能，这个模板更适合你，相应地代码稍微有一点复杂。可以根据情况使用不同的模板。

class UF:
    parent = {}
    size = {}
    cnt = 0
    def __init__(self, M):
        # 初始化 parent，size 和 cnt

    def find(self, x):
        while x != self.parent[x]:
            x = self.parent[x]
            # 路径压缩
            self.parent[x] = self.parent[self.parent[x]];
        return x
    def union(self, p, q):
        if self.connected(p, q): return
        # 小的树挂到大的树上， 使树尽量平衡
        leader_p = self.find(p)
        leader_q = self.find(q)
        if self.size[leader_p] < self.size[leader_q]:
            self.parent[leader_p] = leader_q
        else:
            self.parent[leader_q] = leader_p
        self.cnt -= 1
    def connected(self, p, q):
        return self.find(p) == self.find(q)

并查集的学习与总结

前言

查找资料

学习

总结

附代码(lucifer)

感谢您的支持，我会继续努力的!