[高阶数据结构(一)]并查集详解

1.前言

本系列会带大家走进高阶数据结构的学习, 其中包括并查集,图论, LRU cache, B树, B+树, B*树, 跳表. 其中, 图论中讲解的时间最长, 包括邻接表, 邻接矩阵, 广度优先遍历, 深度优先遍历, 最小生成树中的kruskal算法以及prim算法；最短路径中的dijkstra算法, bellman-Ford算法, Floyd-wars hall算法. 

本章重点

本章着重讲解并查集的原理、并查集的模拟实现以及并查集的相关应用。

2.并查集的原理

在一些应用问题中，需要 将 n 个不同的元素划分成一些不相交的集合 。 开始时，每个元素自成一个 单元素集合，然后按一定的规律将归于同一组元素的集合合并 。在此过程中 要反复用到查询某一 个元素归属于那个集合的运算 。适合于描述这类问题的抽象数据类型称为 并查集 (union-find set) 。

解释：数组中下标对应的-n,负数就表示他是一个集合的组长，n就表示他这个集合有多少人。对于是组长的人来说，那就存储一个负数，而对于非组长的人来说下标里面的值就存储的是组长所在位置的下标。

 那么此时非常凑巧的是，南京和杭州的同学坐在同一辆车上去往该公司，且座位还比较靠近。在坐车闲聊的过程中，相互都认识了，于是就想着将两个集合合并成一个集合，于是就出现了下面的情况

此时,下标为1的位置应该存储它的父亲,也就是0,下标为4.9的位置不能直接存储0,而是应该存储1,因为1才是他们的直系父亲. 可以用下图来表示:

从这里就可以发现了，下标1所在位置的值发生了改变，原来三个集合合并成了两个集合。

0所在的下标由原来的-4变成了-7，而1所在下标的值由-3变成了0。

3.并查集的模拟实现

通过观察上述过程，可以知道你至少要有下面几个函数做支撑：找到一个下标的根（后续合并的操作由根部对应的下标值进行改变）, 合并两个集合, 判断两个树是否在同一个集合。

由于并查集的本质是一个数组，所以基本框架如下：

class UnionFindSet
{
public:
	UnionFindSet(size_t n)
		:_ufs(n, -1)//直接先开辟n个空间，负数表示根，1表示一个节点连接自己
	{}
	//合并并查集
	void Union(int x1, int x2)
	{}
	//查找某个值下标的根下标在哪
	int FindParent(int x)
	{}
	//有几个并查集
	size_t SetSize()
	{}
	//判断两个下标所在的值是否在同一个并查集
	bool SameSet(int x, int y)
	{}
private:
	vector<int> _ufs;
};

首先就是要先写出找到一个下标的根的函数，如下所示

//查找某个值下标的根下标在哪
int FindParent(int x)
{
	int parent = x;
	while (_ufs[parent] >= 0)
		parent = _ufs[parent];
	//如果合并太多，可能导致并查集太高，所以通过压缩高度，修改合并之后某些值的父亲指向
	while (_ufs[x] >= 0)
	{
		int tmp = _ufs[x];
		_ufs[x] = parent;//直接指根节点
		x = tmp;
	}
	return parent;
}

代码分为两步,第一步就是在找它的根,就是一直向前找直到遇见负数.第二部分的代码在进行路径压缩工作,若是有多个集合进行合并,那么我们的树可能就会很高,查找最下面的树的根时,就会出现效率低下的问题,所以进行路径压缩很有必要. 关于路径压缩的原理如下:

当我下次找4的时候，时间就变少了。

接下来就是合并两个并查集的代码：(数据少的集合，向数据多的集合里面合并)

//合并并查集
void Union(int x1, int x2)
{
	int root1 = FindParent(x1);
	int root2 = FindParent(x2);
	if (root1 == root2) return;
	if (abs(_ufs[root1]) >= abs(_ufs[root2]))
	{
		_ufs[root1] += _ufs[root2];
		_ufs[root2] = root1;
	}
	else
	{
		_ufs[root2] += _ufs[root1];
		_ufs[root1] = root2;
	}
}

最后就是告诉外部，现在有几个集合的代码了

//有几个并查集
size_t SetSize()
{
	size_t n = 0;
	for (int i = 0; i < _ufs.size(); i++)
	{
		if (_ufs[i] < 0)
			n++;
	}
	return n;
}

最后给出整体代码，相关注释均在里面，不懂的小伙伴可以后台T我

class UnionFindSet
{
public:
	UnionFindSet(size_t n)
		:_ufs(n, -1)//直接先开辟n个空间，负数表示根，1表示一个节点连接自己
	{}
	//合并并查集
	void Union(int x1, int x2)
	{
		int root1 = FindParent(x1);
		int root2 = FindParent(x2);
		if (root1 == root2) return;
		if (abs(_ufs[root1]) >= abs(_ufs[root2]))
		{
			_ufs[root1] += _ufs[root2];
			_ufs[root2] = root1;
		}
		else
		{
			_ufs[root2] += _ufs[root1];
			_ufs[root1] = root2;
		}
	}
	//查找某个值下标的根下标在哪
	int FindParent(int x)
	{
		int parent = x;
		while (_ufs[parent] >= 0)
			parent = _ufs[parent];
		//如果合并太多，可能导致并查集太高，所以通过压缩高度，修改合并之后某些值的父亲指向
		while (_ufs[x] >= 0)
		{
			int tmp = _ufs[x];
			_ufs[x] = parent;//直接指根节点
			x = tmp;
		}
		return parent;
	}
	//有几个并查集
	size_t SetSize()
	{
		size_t n = 0;
		for (int i = 0; i < _ufs.size(); i++)
		{
			if (_ufs[i] < 0)
				n++;
		}
		return n;
	}
	//判断两个下标所在的值是否在同一个并查集
	bool SameSet(int x, int y)
	{
		return FindParent(x) == FindParent(y);
	}
private:
	vector<int> _ufs;
};

4.并查集的应用

1.LCR 116. 省份数量 - 力扣（LeetCode）

这道问题就是在问你，有几个集合。

不多说直接上代码

class UnionFindSet
{
private:
    vector<int> _ufs;
public:
    UnionFindSet(size_t n)
        :_ufs(n,-1)
        {}
    int FindRoot(const int& val)
    {
        int root=val;
        while(_ufs[root]>=0)
            root=_ufs[root];
        return root;
    }
    void Union(int x,int y)
    {
        int root1=FindRoot(x);
        int root2=FindRoot(y);
        if(root1==root2) return;
        _ufs[root1]+=_ufs[root2];
        _ufs[root2]=root1;
    }
    int SetSize()
    {
        int ret=0;
        for(auto e:_ufs)
            if(e<0) ret++;
        return ret;
    }
};
class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n=isConnected.size();
        UnionFindSet ufs(n);
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                if(isConnected[i][j]) ufs.Union(i,j);
            }
        }
        return ufs.SetSize();
    }
};

并查集的题目还有很多，这里就不一 一列举了，有兴趣可以去牛客，leedcode上面看看。 

5.总结

并查集相对来说是属于高阶数据结构里面比较简单的了，但是也是比较重要的一个部分。在求职过程中也会经常遇到并查集相关的考点，希望各位小伙伴能够好好学习，打下坚实的基础。