首页 > 代码库 > <算法><Union Find并查集>

<算法><Union Find并查集>

Intro

  • 想象这样的应用场景:给定一些点,随着程序输入,不断地添加点之间的连通关系(边),整个图的连通关系也在变化。这时候我们如何维护整个图的连通性(即判断任意两个点之间的连通性)呢?
  • 一个比较简单的solution是每个点都有一个便签,标记它属于哪个连通子图。这种做法就有一个很明显的问题 -- 牵一发而动全身,因为每个节点所属的组号(标签)都是单独记录,各自为政的,没有将它们以更好的方式组织起来,当涉及到修改的时候,除了逐一通知、修改,别无他法。所以现在的问题就变成了,如何将节点以更好的方式组织起来,组织的方式有很多种,但是最直观的还是将组号相同的节点组织在一起,想想所学的数据结构,什么样子的数据结构能够将一些节点给组织起来?常见的就是链表,图,树,什么的了。但是哪种结构对于查找和修改的效率最高?毫无疑问是树,因此考虑如何将节点和组的关系以的形式表现出来。

Union Find

  • 采用parent-link的方式将节点组织起来,那么节点的root就是该组的组号了。
  • 树这种数据结构容易出现极端情况,因为在建树的过程中,树的最终形态严重依赖于输入数据本身的性质,比如数据是否排序,是否随机分布等等。比如在输入数据是有序的情况下,构造的BST会退化成一个链表
  • 为了解决上述问题,BST可以演变成为红黑树或者AVL树等等。

<算法><Union Find并查集>