[奇怪但有用的数据结构]并查集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 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

洛谷 P3802 小魔女帕琪

题目背景 从前有一个聪明的小魔女帕琪,兴趣是狩猎吸血鬼。 帕琪能熟练使用七种属性(金、木、水、火、土、日、月)的魔法,除了能使用这么多种属性魔法外,她还能将两种...

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

洛谷P1450 [HAOI2008]硬币购物

题目描述 硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西,去了tot次。每次带di枚ci硬币,买si的价值的东西。请问每次有多少种付...

2434
来自专栏机器学习算法全栈工程师

最长公共子序列与最长公共子串

0. 引言 最近鄙人面试百度,出了这道求解公子序列长度的算法题。故此总结一下,这是一个很典型的题目,希望对大家将来的面试中能起到学习的作用。 1. 问题描述 子...

35111
来自专栏ACM算法日常

POJ 3273 | Monthly Expense 农场的窘境(经典二分)

Farmer John is an astounding accounting wizard and has realized he might run out...

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

P2280 [HNOI2003]激光炸弹

题目描述 ? 输入输出格式 输入格式: 输入文件名为input.txt 输入文件的第一行为正整数n和正整数R,接下来的n行每行有3个正整数,分别表示 输...

2735
来自专栏算法修养

POJ 1964&HDU 1505&HOJ 1644 City Game(最大0,1子矩阵和总结)

最大01子矩阵和,就是一个矩阵的元素不是0就是1,然后求最大的子矩阵,子矩阵里的元素都是相同的。 这个题目,三个oj有不同的要求,hoj的要求是5s,...

2874
来自专栏小樱的经验随笔

图的基本算法(BFS和DFS)

图是一种灵活的数据结构,一般作为一种模型用来定义对象之间的关系或联系。对象由顶点(V)表示,而对象之间的关系或者关联则通过图的边(E)来表示。 图可以分为有向图...

2505
来自专栏程序猿DD

第四章 正则表达式回溯法原理

第四章 正则表达式回溯法原理 学习正则表达式,是需要懂点儿匹配原理的。 而研究匹配原理时,有两个字出现的频率比较高:“回溯”。 听起来挺高大上,确实还有很多人...

2006
来自专栏King_3的技术专栏

leetcode-661-Image Smoother

852
来自专栏freesan44

python 算法开发笔记

992

扫码关注云+社区