这一节我们来学习什么是森林。what？这个？当然不是啦，我们都知道植物界里的森林，是由许多棵树组成的，就像上面这张图。在数据结构里的森林是由若干棵互不相交的树组成。下图就是一个由两棵树组成的森林。两棵树之间分别独立，没有交集。那么并查集又是什么呢？在计算机科学中，并查集（Merge-FindSet），也被称为不相交集合（DisjointSet），是用于解决若干的不相交集合的如下几种操作的统称：MAKE-SET(x)：即初始化操作，建立一个只包含元素x的集合。UNION(x,y)：即合并操作，将包含x和y的集合合并为一个新的集合。FIND-SET(x)：即查询操作，计算x所在的集合。并查集通常同时指代不相交集合的数据结构及其对应的算法，其在有些教材中的英文名称也叫做DisjointSetUnion，表示用于求不相交集合并集的相关算法。在本章我们从森林开始讲起，介绍森林的基本概念和遍历方法。之后会讲解一种用于不相交集合的合并运算的数据结构——并查集。并查集通常用森林来实现，并通过记录父节点维护森林的结构信息。最后用并查集解决一道难题。
点击阅读原文快来学习新课程吧！
预览时标签不可点收录于话题#个上一篇下一篇