[奇怪但有用的数据结构]并查集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分了。

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

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

洛谷P3177 [HAOI2015]树上染色(树上背包)

比较套路吧,设\(f[i][j]\)表示以\(i\)为根的子树中选了\(j\)个黑点对答案的贡献

831
来自专栏数据结构与算法

2017.5.26暴力赛解题报告

预计分数:T1:40AC+60TLE      T2:40AC+60TLE        T3:10AC+90TLE      总分=90 实际分数:T1:10...

3796
来自专栏HansBug's Lab

1934: [Shoi2007]Vote 善意的投票

1934: [Shoi2007]Vote 善意的投票 Time Limit: 1 Sec  Memory Limit: 64 MB Submit: 1174  ...

2737
来自专栏HansBug's Lab

1624: [Usaco2008 Open] Clear And Present Danger 寻宝之路

1624: [Usaco2008 Open] Clear And Present Danger 寻宝之路 Time Limit: 5 Sec  Memory L...

3256
来自专栏aCloudDeveloper

string 之 strlen函数

Author: bakari  Date: 2012/8/9 近两年好多的IT公司喜欢拿一些库函数来考,string函数库当然是首选,除此之外,像qsort,S...

1887
来自专栏HansBug's Lab

3391: [Usaco2004 Dec]Tree Cutting网络破坏

3391: [Usaco2004 Dec]Tree Cutting网络破坏 Time Limit: 1 Sec  Memory Limit: 128 MB Su...

32510
来自专栏HansBug's Lab

1112: [POI2008]砖块Klo

1112: [POI2008]砖块Klo Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 1245  Solv...

3216
来自专栏玄魂工作室

56行Python代码实现身份证字典生成器

最近过生日,女朋友送了几本Python黑客编程的书(没错,小黑阔也是可以有女朋友的)。哈哈,皮一下就是很开心。

1633
来自专栏tkokof 的技术,小趣及杂念

侃侃哈希表

说到哈希表,相信初通数据结构的人士应该耳熟能详,其相关的结构细节虽然并不繁复,但就快速查找数据而言,该结构优异的性能表现绝对可算一枝独秀,平均情况下O(1)的时...

681
来自专栏数据结构与算法

BZOJ2152: 聪聪可可(点分治)

聪聪和可可是兄弟俩,他们俩经常为了一些琐事打起来,例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑(可是他们家只有一台电脑)……遇到这种问题,一般情况...

903

扫码关注云+社区