Info
新版网站会员 即将涨价;已支持老用户续费~
读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
LeetCode | 力扣 | 难度 |
---|---|---|
130. Surrounded Regions | 130. 被围绕的区域 | 🟠 |
323. Number of Connected Components in an Undirected Graph🔒 | 323. 无向图中连通分量的数目🔒 | 🟠 |
990. Satisfiability of Equality Equations | 990. 等式方程的可满足性 | 🟠 |
记得我之前在讲 图论算法基础 时说图论相关的算法不会经常考,但最近被打脸了,因为一些读者和我反馈近期求职面试涉及很多图论相关的算法,可能是因为环境不好所以算法这块更卷了吧。
常见的图论算法我都已经写过了,这里按难度顺序列举一下:
并查集(Union-Find)算法是一个专门针对「动态连通性」的算法,我之前写过两次,因为这个算法的考察频率高,而且它也是最小生成树算法的前置知识,所以我整合了本文,争取一篇文章把这个算法讲明白。
首先,从什么是图的动态连通性开始讲。
一、动态连通性
简单说,动态连通性其实可以抽象成给一幅图连线。比如下面这幅图,总共有 10 个节点,他们互不相连,分别用 0~9 标记:
![](/algo/images/unionfind/1.jpg)
现在我们的 Union-Find 算法主要需要实现这两个 API:
class UF {
// 将 p 和 q 连接
public void union(int p, int q);
// 判断 p 和 q 是否连通
public boolean connected(int p, int q);
// 返回图中有多少个连通分量
public int count();
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
class UF {
public:
// 将 p 和 q 连接
virtual void union(int p, int q) = 0;
// 判断 p 和 q 是否连通
virtual bool connected(int p, int q) = 0;
// 返回图中有多少个连通分量
virtual int count() = 0;
};
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
class UF:
# 将 p 和 q 连接
def union(self, p, q):
pass # 将 p 和 q 连接的逻辑在这里
# 判断 p 和 q 是否连通
def connected(self, p, q):
pass # 判断 p 和 q 是否连通的逻辑在这里
# 返回图中有多少个连通分量
def count(self):
pass # 返回图中有多少个连通分量的逻辑在这里
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
type UF struct{}
// 将 p 和 q 连接
func (uf *UF) Union(p int, q int) {}
// 判断 p 和 q 是否连通
func (uf *UF) Connected(p int, q int) bool {
return false
}
// 返回图中有多少个连通分量
func (uf *UF) Count() int {
return 0
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
var UF = function() {
// 将 p 和 q 连接
this.union = function(p, q) {};
// 判断 p 和 q 是否连通
this.connected = function(p, q) {};
// 返回图中有多少个连通分量
this.count = function() {};
};
这里所说的「连通」是一种等价关系,也就是说具有如下三个性质:
1、自反性:节点 p
和 p
是连通的。
2、对称性:如果节点 p
和 q
连通,那么 q
和 p
也连通。
3、传递性:如果节点 p
和 q
连通,q
和 r
连通,那么 p
和 r
也连通。
比如说之前那幅图,0~9 任意两个不同的点都不连通,调用 connected
都会返回 false,连通分量为 10 个。
如果现在调用 union(0, 1)
,那么 0 和 1 被连通,连通分量降为 9 个。
再调用 union(1, 2)
,这时 0,1,2 都被连通,调用 connected(0, 2)
也会返回 true,连通分量变为 8 个。
![](/algo/images/unionfind/2.jpg)
判断这种「等价关系」非常实用,比如说编译器判断同一个变量的不同引用,比如社交网络中的朋友圈计算等等。
这样,你应该大概明白什么是动态连通性了,Union-Find 算法的关键就在于 union
和 connected
函数的效率。那么用什么模型来表示这幅图的连通状态呢?用什么数据结构来实现代码呢?