-
并查集（Union-Find）
并查集（Union-Find）
并查集是一种树型的数据结构，它的特点是由子结点找到父亲结点，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。
并查集通过一个一维数组来实现，其本质是维护一个森林。并查集解决单个问题（添加，合并，查找）的时间复杂度都是O(1)。
N 个元素的集合，通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。
二、并查集的代码实现
1、集合树用字典存储的定义
并查集使用的是字典来存储树，字典的键是子节点，值是父节点。
注：与二叉树、链表不同，二叉树、链表是键是父节点，值为子节点。class UnionFind: def __init__(self): """ 记录每个节点的父节点 """ self.father = {} # self.value = {} 如果边有权重 # key 本节点名称 ，value 为本节点 到 根点的权值- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
2、初始化(添加元素)
当把一个新节点添加到并查集中，它的父节点应该是空。
def add(self,x): ''' 添加新节点 ''' if x not in self.father: self.father[x] = None- 1
- 2
- 3
- 4
- 5
- 6
3、合并两个节点
合并联通的节点，如果他们是同属于一棵树的，则任选一个节点作为另一个节点的父节点。如果他们的根是不同的，则让一个树的根节点作为另一个树的根节点的父节点。
def merge(self,x,y): ''' 合并两个节点 ''' root_x, root_y = self.find(x), self.find(y) # 查找节点 x，y 的根节点 if root_x != root_y: # 根节点不同，则合并 self.father[root_x] = root_y- 1
- 2
- 3
- 4
- 5
- 6
- 7
4、查找一个节点的根节点
查找一个根节点的方法是：如果节点的父节点不为空，那么就不断迭代。
def find(self,x): ''' 查找根节点 ''' root = x while self.father[root] != None: root = self.father[root] return root- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
5、路径压缩
这里有一个优化的点：如果我们树很深，比如说退化成链表，那么每次查询的效率都会非常低。所以我们要做一下路径压缩。也就是把树的深度固定为二。
这么做可行的原因是，并查集只是记录了节点之间的连通关系，而节点相互连通只需要有一个相同的根节点（祖先）就可以了。
路径压缩可以用递归，也可以迭代。这里用迭代的方法。
def find(self,x): ''' 查找根节点 ''' root = x while self.father[root] != None: root = self.father[root] #路径压缩 while x != root: original_father = self.father[x] self.father[x] = root x = original_father return root- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
6、两节点是否连通
我们判断两个节点是否处于同一个连通分量的时候，就需要判断它们的根节点（祖先）是否相同。
def is_connected(self,x,y): ''' 判断两节点是否联通 ''' return self.find(x) = self.find(y)- 1
- 2
- 3
- 4
- 5
并查集 Python 代码的实现
class UnionFind: def __init__(self): ''' 记录每个节点的父节点----字典的格式，字典的键是子节点，值是父节点。 ''' self.father = {} # self.value = {} 如果边有权重 # key 本节点名称 ，value 为本节点 到 根点的权值 def add(self,x): ''' 添加新节点---------当把一个新节点添加到并查集中，它的父节点应该为空 ''' if x not in self.father: self.father[x] = None def merge(self,x,y,val): ''' 合并两个节点-------如果发现两个节点是连通的（两个节点被一个边连接起来），那么就要把他们合并。然后如果他们的根是相同的（同属一棵树），则任选一个节点作为另一个结点的父节点。这里究竟把谁当做父节点一般是没有区别的。如果他们的根是不同的，则让一个树的根节点作为另一个数的根节点的父节点。 ''' root_x,root_y = self.find(x),self.find(y) #查找节点x，y的跟根节点 if root_x != root_y: self.father[root_x] = root_y def find(self,x): ''' 查找根节点----查找一个节点的根节点方法是：如果节点的父节点不为空，那就不断迭代 ''' root = x while self.father[root] != None: root = self.father[root] #return root #路径压缩，有递归和迭代的方法 while x != root: orginal_father = self.father[x] self.father[x] = root x = orginal_father return root def is_connected(self,x,y): ''' 判断两节点是否相连-------我们判断两个节点是否处于同一个连通分量的时候，就需要判断它们的根节点（祖先）是否相同 ''' return self.find(x) == self.find(y)- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
以整数 0~9 表示 10 个点，连通的数据：[(4, 3), (3, 8), (6, 5), (9, 4), (2, 1), (8, 9), (5, 0), (7, 2), (6, 1), (6, 7)]
每个点的值为其初始组别：element 0 1 2 3 4 5 6 7 8 group number 0 1 2 3 4 5 6 7 8 “并”的操作：(4, 3) 将点 4 和 3 的合并成一组：
element 0 1 2 3 4 5 6 7 8 group number 0 1 2 3 3 5 6 7 8 “查”的操作：找到点对中两个点所在的组别，看是否相同。
Quick-Find 算法
元素和组别之间的一一对应关系可以用“键值对”的存储方式实现。
def con_eleGroupNum(eleList): """ construct the element-group number map :param eleList: the list of distinct elements :return: the dictionary with the form {element: group number} """ result = {} num = 1 for i in eleList: result[i] = num num += 1 return result- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
因为可以直接找到“键”，并通过“键”访问其对应的值，所以查询的复杂度为O(1)。
但是如果是并呢？因为不知道到底是哪些“键”（点）对应着某个“值”（组别），所以需要对整个列表进行遍历，逐一修改。假设现在有 N个点，需要添加的路径由 M 个点对组成，那么“并”的时间复杂度为O(MN)。在数据量极大的情况下，平方级别的算法是有问题的。下面的代码展示了根据一个点对修改组别（合并）的过程，我们以每次点对元素的最小值为新的组别：
def change_GroupNum(pairGroupNum, eleGroupNum): """ connect :param pairGroupNum: the two group numbers of the pair of elements :param eleGroupNum: the dictionary with the form {element: group number} :return: None """ newGroupNum = min(pairGroupNum) for i in eleGroupNum: if eleGroupNum[i] == pairGroupNum[0] or eleGroupNum[i] == pairGroupNum[1]: eleGroupNum[i] = newGroupNum def quick_find(elePair, eleGroupNum): """ find and connect :param elePair: the pair of elements :param eleGroupNum: the dictionary :return: None """ pairGroupNum = (eleGroupNum[elePair[0]], eleGroupNum[elePair[1]]) change_GroupNum(pairGroupNum, eleGroupNum)- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
Quick-Union 算法
为了解决这种低效的并，重新考虑这个问题。现在的关键在于如何能快速地通过一个点找到其相应的组别和这个组中的所有点，并且批量改变这些点的组别。链表，树，图？，比起链表和图，树结构有一个非常“显眼”的根节点，我们可以用它来代表这个树所有节点的组别，修改了根节点，就相当于是修改了全树，此外，树的层次化结构决定了由一个节点查询到组别的过程也是非常高效的。
初始化：每个点看做一棵树，当然这是一棵只有根节点的树，存储了这个节点本身的值作为组别；
查询：对于点对(a,b)，通过a和b向其根节点回溯，判断其所在组别；
合并：若不在同一组别，令其中一个点所在树的根节点成为另一个点的根节点的孩子。这样即便再查询到 a，通过上面的查询过程，程序也会最终判断得到的是现在b的根节点所在的组别，相当于是改变了a所在组的全部元素的组别；
在最坏的情况下，这样的多叉树退化成了一个链表。
能不能尽可能地降低这里的树高呢？也就是说在产生树和合并树的时候就尽量使得每棵树都是“扁平化”的。
大树小树的合并技巧
先看看树的合并，对于我们上面说的这种合并（一棵树的根直接变成另一棵树根的孩子），有一个基本的原则是小树变成大树的子树，会比大树变成小树的子树更加不易增加树高，这一点通过下面的图就能看出来。所以我们可以在生成树的时候，令根节点存储一个属性 weight，用来表示这棵树所拥有的节点数，节点数多的是“大树”，少的就是“小树”。
压缩路径
再看看树的生成，因为每次我们是从树的一个节点回溯到其根节点，所以一个最直接的办法是，将这条路径上的所有中间节点记录下来，全部变成根节点的子节点。但是这样一来会增加算法的空间复杂度（反复开辟内存和销毁）。所以一个备选的思路是每遍历到一个节点，就将这个节点变成他的爷爷节点的孩子（和其父节点在同一层了）。相当于是压缩了查询的路径，频繁的查询当然会导致树的“扁平化”程度更彻底。
经过上面大小树的合并原则以及路径的压缩，其实“并”和“查”两种操作的时间复杂度都非常趋近于O(1)了。
class UFTreeNode(object): def __init__(self, num): # the group number self.num = num # its children self.children = [] # its parent self.parent = None # the number of nodes that rooted by this node self.weight = 1 def genNodeList(eleList): """ generating the node of each element :param eleList: the list of elements :return: a dictionary formed as {element: corresponding node} """ result = {} for ele in eleList: result[ele] = UFTreeNode(ele) return result def locPair(elePair, eleNodeMap): """ locate the positions of the pair of elements :param elePair: :param eleNodeMap: a dictionary formed as {element: corresponding node} :return: the two nodes of the pair of elements """ return [eleNodeMap[elePair[0]], eleNodeMap[elePair[1]]] def backtracking(node): """ 1. find the root of a node 2. cut down the height of the tree :param node: :return: the root of node """ root = node while root.parent: cur = root root = root.parent # the grandfather node of cur exists if cur.parent.parent: # make the father of cur is its grandfather grandfather = cur.parent.parent grandfather.children.append(cur) return root def quickUnion(elePair, eleNodeMap): """ union process :param elePair: :param eleNodeMap: :return: """ nodePair = locPair(elePair, eleNodeMap) root_1, root_2 = backtracking(nodePair[0]), backtracking(nodePair[1]) # if the two elements of the pair are not belongs to the same root (group) if root_1 is not root_2: if root_1.weight >= root_2.weight: # update weight root_1.weight += root_2.weight # make the root2 as a subtree of root1 root_1.children.append(root_2) # update the group number of root2 root_2.num = root_1.num else: root_2.weight += root_1.weight root_2.children.append(root_1) root_1.num = root_2.num- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
547. 省份数量
class Solution: def findCircleNum(self, isConnected: List[List[int]]) -> int: def dfs(i): for j in range(n): if isConnected[i][j] and j not in vis: vis.add(j) dfs(j) n = len(isConnected) vis = set() ans = 0 for i in range(n): if i not in vis: ans += 1 dfs(i) # q = deque([i]) # while q: # i = q.popleft() # for j in range(n): # if isConnected[i][j] and j not in vis: # q.append(j) # vis.add(j) return ans- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
1020. 飞地的数量
1061. 按字典序排列最小的等效字符串
1101. 彼此熟识的最早时间
1102. 得分最高的路径
1135. 最低成本联通所有城市
1168. 水资源分配优化
1202. 交换字符串中的元素
1254. 统计封闭岛屿的数目
1258. 近义词句子
1267. 统计参与通信的服务器
128. 最长连续序列
130. 被围绕的区域
1319. 连通网络的操作次数
1361. 验证二叉树
1391. 检查网格中是否存在有效路径
1489. 找到最小生成树里的关键边和伪关键边
1559. 二维网格图中探测环
1569. 将子数组重新排序得到同一个二叉查找树的方案数
1579. 保证图可完全遍历
1584. 连接所有点的最小费用
1627. 带阈值的图连通性
1631. 最小体力消耗路径
1632. 矩阵转换后的秩
1697. 检查边长度限制的路径是否存在
1722. 执行交换操作后的最小汉明距离
1724. 检查边长度限制的路径是否存在 II
1905. 统计子岛屿
1970. 你能穿过矩阵的最后一天
1998. 数组的最大公因数排序
200. 岛屿数量
2003. 每棵子树内缺失的最小基因值
2076. 处理含限制条件的好友请求
2092. 找出知晓秘密的所有专家
2157. 字符串分组
2204. Distance to a Cycle in Undirected Graph
2307. Check for Contradictions in Equations
261. 以图判树
305. 岛屿数量 II
323. 无向图中连通分量的数目
399. 除法求值
522. 最长特殊序列 II
684. 冗余连接
685. 冗余连接 II
694. 不同岛屿的数量
695. 岛屿的最大面积
711. 不同岛屿的数量 II
721. 账户合并
737. 句子相似性 II
765. 情侣牵手
778. 水位上升的泳池中游泳
785. 判断二分图
803. 打砖块
827. 最大人工岛
839. 相似字符串组
886. 可能的二分法
924. 尽量减少恶意软件的传播
928. 尽量减少恶意软件的传播 II
947. 移除最多的同行或同列石头
952. 按公因数计算最大组件大小
959. 由斜杠划分区域
990. 等式方程的可满足性
LCP 49. 环形闯关游戏
LCS 03. 主题空间
-
相关阅读:
socket编程详解（二）——客户端
理解Java程序的执行
信号槽连接失败原因分析
蓝牙耳机热销榜是哪些？盘点性价比蓝牙耳机排行榜
NestJS 中的 gRPC 微服务通信
眼见为实：关于微服务熔断这几个知识点，你可能理解错了
asp.net酒店餐饮管理系统VS开发sqlserver数据库web结构c#编程Microsoft Visual Studio
Java 基础之线程
JDBC、ORM、mybatis之间的关系
后端统一处理返回前端日期LocalDateTime格式化去T，Long返回前端损失精度问题
- 原文地址：https://blog.csdn.net/weixin_43955170/article/details/125477355
