[奇怪但有用的数据结构]并查集Union Find

严格来讲并查集并不是一个数据结构，而是一个算法，毕竟其英文名直译是联合查找，但作为一个系列，还是当做数据结构讲了。

学术一点讲的话，并查集是用来找一个无向图的联通分量。有这么一个无向图：

无向图

这个图结构有三个联通分量[1, 2 ,3, 8], [4,5]和[6, 7]。接下来以此为例分析一下如何使用并查集算法。

并查集

首先我们有一个parent数组来代表每一个节点的祖先，数组的每一项默认为节点的序号。parent数组一开始就是[0, 1, 2, 3, 4, 5, 6, 7, 8]。

接下来我们有一个关系数组，比如[[1, 2], [2, 3], [1, 8], [4, 5], [6, 7] ]。

Union

对于每一个关系，我们应用一次联合（Union）操作。一个联合操作的流程是这样子的：

1. 对于关系a->b,先通过find找出a和b的祖先parent_a和parent_b,
2. 如果parent_a和parent_b不同，让parent[parent_a] = parent_b

Find

找出一个节点祖先的操作find的流程则是：

1. 如果parent[a] = a,返回a
2. 否则返回find(parent[a])

我们从关系[1, 2]开始，它们的祖先不同，让parent[1] = 2,现在parent数组为[0, 2, 2, 3, 4, 5, 6, 7, 8]。

然后关系[1, 3]，祖先不同，并且1的祖先是2，所以让parent[2] = 3，parent数组为[0, 2, 3, 3, 4, 5, 6 ,7, 8]

然后是关系[1, 8],祖先不同，1的祖先是3(1->2->3)，所以让parent[3] = 8, parent数组为[0, 2, 3, 8, 4, 5, 6, 7, 8]

关系[4, 5]和[6, 7]一样，最后的parent数组为[0, 2, 3, 8, 5, 5, 7, 7, 8]。

这样一个并查集就建立好了，我们可以通过比较祖先判断两个节点是否连通。

计算连通分量数目

如果只是计算连通分量的数量的话，修改一下union操作，每遇到两个节点的祖先不同，连通分量数减一（初始为节点数）。

之前的例子中每一次union操作两个节点的祖先都不同，所以连通分量数为8-5=3， 如果再添加一个关系[2, 8]，2的祖先是8(2->3->8)，8的祖先是自己，祖先相同，这个关系在连通分量[1, 2, 3, 8]中，连通分量数仍为3。

如果在添加一个关系[3, 5]，3的祖先是8，5的祖先是5，连通分量数减一为2，而此时parent[8] = 5，parents数组也变为[0, 2, 3, 8, 5, 5, 6, 7, 8],此时的两个连通分量是[1, 2, 3, 4, 5, 8]和[6, 7]。

改进

另外之前的find操作可以作一步改进，如果parent[a]不为a的话，先将parent[a]赋值为find(parent[a])， 然后再返回，这样可以减少一些递归操作，parents数组最终也只会出现最终的祖先，上面的例子中parent数组最终为[0, 8, 8, 8, 5, 5, 7, 7, 8]。

应用

并查集可应用在社交媒体中判断两个用户是否在同一个圈子中,也可以用于判断两个地点间是否有交通线路。

代码

还是很简单的

class UnionFind:
    def __init__(self, size):
        self.parents = list(range(size))
        self.groupNum = size
    
    def find(self, n):
        if self.parents[n] == n:
            return n
        else:
            self.parents[n] = self.find(self.parents[n])
            return self.parents[n]
        
    def union(self, m, n):
        if self.find(m) != self.find(n):
            self.parents[self.find(m)] = self.find(n)
            self.groupNum -= 1

结语

并查集经常出现在算题题目中，大家应该理解并掌握，最关键的是判断出一个场景是适用于并查集，如果当时PAT考试的时候我看出来最后一题用的是并查集，也能拿98分了。

最后祝大家享受生活，享受代码。