数据结构系列-10 并查集(union find)

2021/11/3 23:09:59

本文主要是介绍数据结构系列-10 并查集(union find),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1.什么是并查集?

并查集(union find)是一种用于跟踪元素的数据结构,它通过一个或者多个不相交的集合来跟踪元素。主要支持两种操作查找find合并union

2.应用:克努斯卡尔最小成成树算法。

参考演示: 最小生成树算法演示_bilibili

通过上面的演示,能更好的理解什么是并查集,和并查集的用法

3.如何创建并查集

首先需要在元素和整数之间[0,n),简历一个映射关系

数组下标,代表元素,值代表父元素(组),开始时,父元素就是下标自己。

注意,本步骤并非必须,但是它可以帮助我们构建一个基于数组的并查集

 4.合并操作

查找,为了查找某个节点,不断查找节点的父节点,一直找到根节点(父节点指向自己)

为了将两个元素合并,只要找到这两个元素的根节点,如果根节点不同,就将其中一个根节点指向另外一个节点的根节点。通常将元素少的组合并入元素多的组。

5.注意:

  • 对于并查集我们通常不做 分开(un-union)操作
  • 组的数量等于根节点的数量。并且,组的数量只会减少,不会增加

6.并查集路径压缩(再寻找某个元素的根节点时执行)

  1. 找到某个元素的,根节点。
  2. 它所有父节点的,以及它自己的父节点都设置成根节点。

7. go语言代码实现



这篇关于数据结构系列-10 并查集(union find)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程