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

相关文章

来自专栏c#开发者

Clean up your BizTalk databases

Here are a few scripts / stored procedures that most of the Biztalk newbies woul...

3434
来自专栏曾大稳的博客

MediaCodec硬编码pcm2aac

MediaCodec是Android(api>=16)提供的一个多媒体硬解编码库,能实现音视频的编解码。

1302
来自专栏Pulsar-V

Save Camera Document

#pragma once #include "HCCamera.h" #include <time.h> #include <cstdio> #incl...

2828
来自专栏跟着阿笨一起玩NET

c# 使用timer定时器操作,上次定时到了以后,下次还未执行完怎么处理

------解决方案-------------------------------------------------------- 开始的时候,禁用定时器,你...

2631
来自专栏JMCui

MongoDB系列五(地理空间索引与查询).

Volvo Today, Volvo announced i...

2712
来自专栏Ryan Miao

ehcache报错

jfinal2.0+tomcat7+ehcache2.6.11+Linux Linux version 2.6.18-164.el5 (mockbuild@x8...

3729
来自专栏IT杂记

Storm客户端提交任务失败原因分析

2550
来自专栏linux驱动个人学习

高通msm8909耳机调试

1、DTS相应修改: DTS相关代码:kernel/arch/arm/boot/dts/qcom/msm8909-qrd-skuc.dtsi: 1 s...

7465
来自专栏linux驱动个人学习

高通Audio中ASOC的machine驱动

ASoC被分为Machine、Platform和Codec三大部分,其中的Machine驱动负责Platform和Codec之间的耦合以及部分和设备或板子特定的...

9714
来自专栏前端儿

Web 前端颜色值--字体--使用,整理整理

颜色值 CSS 颜色使用组合了红绿蓝颜色值 (RGB) 的十六进制 (hex) 表示法进行定义。对光源进行设置的最低值可以是 0(十六进制 00)。最高值是 2...

2272

扫码关注云+社区