为什么重来不写算法博客的我今天要写个算法博客呢?因为数据结构课设老师要求我是真的没有任何办法。

何为并查集?网上说他是树,但我觉得不是,他就是个串。

如图所示就是两个集合

并查集的集合和数学上的不太一样,每个元素之间都是有关联的,这也牵扯到并查集的作用,你可以随便抓住一个元素,找到它集合的头。那找到头有什么用呢?很简单,如果两个元素的头一样,就能说明他们是同一个并查集的,如果不一样就说明不是。实际应用中这种场景可以用在族谱表中,路线判断联通与否中,组织层级关系中等等。

那先从初始化讲起,最开始的元素,肯定是互不相关的,我们要给他们之间牵线,找头。但在我们牵线找头之前,他们需要一个初始状态,这个状态不难想象,就是让他们自己成为自己的头。

另外说一句,之所以我一开始说和树不太一样,是因为如果你要写成树,必然有很好的拓展性,但是占用资源太多了,而且你在查找头的时候,传参也是一个问题,因为你无法一下子获取节点

简单解释一下怎么用数组来存储,这里的思想类似于散列表,数组的下标为该点,数组对应的值为该点的父节点(姑且这么叫他),那我们可以用递归的思想,去找该点父节点的父节点的父节点的父节点以此类推找到他的祖宗。

初始化如下,甚至不需要个括号:

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;
}