跳至主要內容

 

labuladong原创并查集图论算法数据结构约 5227 字大约 17 分钟

Info

新版网站会员open in new window 限时优惠;算法可视化编辑器上线,点击体验open in new window

读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:

LeetCode力扣难度
130. Surrounded Regionsopen in new window130. 被围绕的区域open in new window🟠
323. Number of Connected Components in an Undirected Graphopen in new window🔒323. 无向图中连通分量的数目open in new window🔒🟠
990. Satisfiability of Equality Equationsopen in new window990. 等式方程的可满足性open in new window🟠

记得我之前在讲 图论算法基础 时说图论相关的算法不会经常考,但最近被打脸了,因为一些读者和我反馈近期求职面试涉及很多图论相关的算法,可能是因为环境不好所以算法这块更卷了吧。

常见的图论算法我都已经写过了,这里按难度顺序列举一下:

  1. 图论算法基础
  2. 二分图判定算法及应用
  3. 环检测/拓扑排序算法及应用
  4. 并查集算法及应用(本文)
  5. Kruskal 最小生成树算法及应用
  6. Prim 最小生成树算法及应用
  7. Dijkstra 算法模板及应用

并查集(Union-Find)算法是一个专门针对「动态连通性」的算法,我之前写过两次,因为这个算法的考察频率高,而且它也是最小生成树算法的前置知识,所以我整合了本文,争取一篇文章把这个算法讲明白。

首先,从什么是图的动态连通性开始讲。

一、动态连通性

简单说,动态连通性其实可以抽象成给一幅图连线。比如下面这幅图,总共有 10 个节点,他们互不相连,分别用 0~9 标记:

现在我们的 Union-Find 算法主要需要实现这两个 API:

java 🟢
class UF {
    /* 将 p 和 q 连接 */
    public void union(int p, int q);
    /* 判断 p 和 q 是否连通 */
    public boolean connected(int p, int q);
    /* 返回图中有多少个连通分量 */
    public int count();
}

这里所说的「连通」是一种等价关系,也就是说具有如下三个性质:

1、自反性:节点 pp 是连通的。

2、对称性:如果节点 pq 连通,那么 qp 也连通。

3、传递性:如果节点 pq 连通,qr 连通,那么 pr 也连通。

比如说之前那幅图,0~9 任意两个不同的点都不连通,调用 connected 都会返回 false,连通分量为 10 个。

如果现在调用 union(0, 1),那么 0 和 1 被连通,连通分量降为 9 个。

再调用 union(1, 2),这时 0,1,2 都被连通,调用 connected(0, 2) 也会返回 true,连通分量变为 8 个。

判断这种「等价关系」非常实用,比如说编译器判断同一个变量的不同引用,比如社交网络中的朋友圈计算等等。

这样,你应该大概明白什么是动态连通性了,Union-Find 算法的关键就在于 unionconnected 函数的效率。那么用什么模型来表示这幅图的连通状态呢?用什么数据结构来实现代码呢?

加载中...

上次编辑于: