并查集(Union-Find)算法解析

符号 阅读:385 2020-10-19 15:34:36 评论:0

最近用到了并查集,记录一下。主要还是对应用场景进行分析建模,判断是否可以使用并查集。

 

并查集算法主要用于判断连通性。典型的应用场景很多,举例:

1. 网络连通判断。如,已知部分临散的点连通,判断整个网络是否连通。

2. 变量名等同性。在程序中,可以声明多个引用来指向同一对象,这个时候就可以通过为程序中声明的引用和实际对象建立动态连通图来判断哪些引用实际上是指向同一对象。

3. 金属渗透建模。金属可以理解为一个二维矩阵,金属是否可以导电,需要判断是两端是否连通。

 

并查集使用数组来维护一个树状结构。主要有3个操作:

(1) union, 连通2个点。合并到一个分支。

(2) connected,判断2个节点是否位于同一个分支,也就是是否连通。

(3) find, 获取当前节点所在的分支。

 

union实现的不同,耗时差异大。这点需要注意,保持树的深度不要恶化。

声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
排行榜
KIKK导航

KIKK导航

关注我们