[数据结构4.6]树的应用

并查集

一种简单的集合表示。

通常用树的双亲表示法作为并查集的存储结构。

通常用数组元素的下标代表元素名，用根结点的下标代表子集合名，根结点的双亲结点为负数。


常用方法：

Initial(S)：将集合S中的每个元素都初始化为只有一个单元素的子集合。

Union(S,Root1,Root2)：把集合S中的子集合(互不相交)ROOT2并入子集合ROO1。

Find(S,x)：查找集合S中单元素x所在子集合，并返回该子集合的名字。


并查集示意



章节小节回顾


小节回顾
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容