【图论】并查集(Union-find Sets)

前言
一、并查集(Union-find Sets)
- 基本概念
- 基本操作步骤
二、并查集的操作步骤
- 1. 初始化 `init`
- 2. 查询 `find`、合并 `union`（未进行路径压缩）
- 3. 查询 `find`、合并 `union`（路径压缩）
三、Kruskal 算法中 `环` 的判断
- 并查集的使用
总结

前言

在使用 Kruskal 算法求解最小生成树的时候，需要用到并查集(Union-find Sets)，所以记录下并查集的操作与代码。

并查集在最小生成树算法中的使用

并查集的基本概念和基本代码

这两个视频讲解的比较清楚。

并查集(Union-find Sets)是一种非常精巧而实用的数据结构，它主要用于处理一些不相交集合的合并问题。一些常见的用途有求连通子图、求最小生成树的 Kruskal 算法和求最近公共祖先(LCA)等。
在无向图中，判断一条边加入后是否形成环可以通过检查该边连接的两个节点是否已经连通来实现。如果这两个节点在加入这条边之前已经是连通的，那么加入这条边后就会形成环。
使用并查集（Union-Find）数据结构来高效地判断两个节点是否连通。并查集支持两种操作：查找（Find）和合并（Union）。查找操作可以确定一个元素属于哪个子集，合并操作可以将两个子集合并成一个子集。

一般初始化时都将每个节点的父亲节点设置为自己

fa = []
def init(n):for i in range (1,n+1):fa[i]= i

假如有编号为 $1, 2, 3, \dots, n$ 的 $n$ 个元素，我们用一个数组 $f a []$ 来存储每个元素的父节点。一开始，我们先将它们的父节点设为自己。

在这里插入图片描述

找到 $i$ 的父亲节点直接返回，未进行路径压缩：

查询 find

def find(fa, i):if fa[i] == i:return ireturn find(fa, fa[i])

这是一个递归函数，递归出口是：到达父亲节点位置，就返回父亲节点，否则不断地往上查找父亲节点。

合并 union

def union(fa, i, j):# 查找两个节点的父亲节点root1 = find(fa, i)  # 找到 i 的父亲节点root2 = find(fa, j)  # 找到 j 的父亲节点fa[root1] = root2    # 将 i 的父亲节点指向 j 的父亲节点

运行以下代码：

union(4,3)    # 将 4 的父亲节点指向 3 的父亲节点
union(3,2)    # 将 3 的父亲节点指向 2 的父亲节点
union(2,1)    # 将 2 的父亲节点指向 1 的父亲节点

得到：
在这里插入图片描述
若运行union(4,5)，意思是将 4 的父亲节点指向 5 的父亲节点。代码中需要不断地 find，查找 4 的父亲节点，直到查找到 4 的父亲节点为 1 ，才将 1 的父亲节点指向 5。

类似于：
在这里插入图片描述
需要查找 3 次，才能查找到父亲节点。

union(4,6) ——— 需要查找 4 次；
union(4,7) ——— 需要查找 5 次；
.
.
union(4,10000) ——— 需要查找 9998 次；

时间复杂度较高。

找到 $i$ 的父亲节点后，更新 $i$ 的父亲节点，进行了路径压缩：

查询 find

def find(fa, i):if fa[i] == i:return ielse:fa[i] = find(fa, fa[i])    # 路径压缩return fa[i]

合并 union

def union(fa, i, j):# 查找两个节点的父亲节点root1 = find(fa, i)  # 找到 i 的父亲节点root2 = find(fa, j)  # 找到 j 的父亲节点fa[root1] = root2    # 将 i 的父亲节点指向 j 的父亲节点

运行以下代码：

union(4,3)    # 将 4 的父亲节点指向 3 的父亲节点
union(3,2)    # 将 3 的父亲节点指向 2 的父亲节点
union(2,1)    # 将 2 的父亲节点指向 1 的父亲节点

得到：

在这里插入图片描述
若运行union(4,5)，意思是将 4 的父亲节点指向 5 的父亲节点。因为在之前的代码中已经将 4 的父亲节点更新为 1，所以直接将 1 的父亲节点指向 5 ，代码就运行结束了。

在 Kruskal 算法中，初始化每个节点为一个独立的树（父亲节点都是自己，互不相同）。
那么如何判断加入一条边后会不会形成环呢？
- 如果这条边的两个节点属于两棵不同的树，那么加入后一定不会形成环（父亲节点不相等，就不会形成环）；
- 如果这条边的两个节点属于同一棵树，那么加入后就会形成环（父亲节点相等，就会形成环）。
所以判断加入一条边后会不会形成环，只需要判断这条边的两个节点的父亲节点是否相等即可。