为什么重来不写算法博客的我今天要写个算法博客呢?因为数据结构课设老师要求我是真的没有任何办法。
何为并查集?网上说他是树,但我觉得不是,他就是个串。

并查集的集合和数学上的不太一样,每个元素之间都是有关联的,这也牵扯到并查集的作用,你可以随便抓住一个元素,找到它集合的头。那找到头有什么用呢?很简单,如果两个元素的头一样,就能说明他们是同一个并查集的,如果不一样就说明不是。实际应用中这种场景可以用在族谱表中,路线判断联通与否中,组织层级关系中等等。
那先从初始化讲起,最开始的元素,肯定是互不相关的,我们要给他们之间牵线,找头。但在我们牵线找头之前,他们需要一个初始状态,这个状态不难想象,就是让他们自己成为自己的头。
另外说一句,之所以我一开始说和树不太一样,是因为如果你要写成树,必然有很好的拓展性,但是占用资源太多了,而且你在查找头的时候,传参也是一个问题,因为你无法一下子获取节点
简单解释一下怎么用数组来存储,这里的思想类似于散列表,数组的下标为该点,数组对应的值为该点的父节点(姑且这么叫他),那我们可以用递归的思想,去找该点父节点的父节点的父节点的父节点以此类推找到他的祖宗。
初始化如下,甚至不需要个括号:
for(int i = 0 ; i<Set_Size ; i++)
Set[i] = i;
查找如下,模块短小直接内联:
inline int Find(int Number)
{
if (Number == Set[Number])
return Number;
else
return Find(Set[Number]);
}
融合如下,模块更短小还是内联
inline void Merge(int Number_1 , int Number_2)
{
Set[Find(Number_2)] = Number_1;
}
发表评论