微信大概是我们每天必须接触的一个APP之一,公交上、地铁上、工作休息时,刷刷朋友圈,看看好友当天经历了什么。相较于QQ,微信的一个特点之一就是:除非好友的好友也是你的好友,否则你在朋友圈里看不到好友的好友对好友朋友圈的点赞和评论。
LeetCode上,有一道名为“朋友圈”的题目:
不过题目的要求和微信朋友圈不一样。题目说明,如果A和B是朋友,B和C是朋友,那么A和C也是朋友,即朋友圈中的友谊具有传递性。这里的朋友圈也就是朋友的集合。
如何来求解这个题目呢?那就要用到一个用于表示集合内元素关系的数据结构——并查集。
并查集
并查集是一种处理不相交集合的合并及查询问题的数据结构。一些常见的用途有求连通子图、求最小生成树的 Kruskal 算法等。换言之,并查集是一种树形结构,可以用来回答两个元素是否连接的问题。即,通过并查集算法,可以将两个不相连的元素连接起来,也可以查询两个元素是否已连接。这里的“连接”的含义是,两个元素是否具有同一个“根”(从这个角度可以理解,为什么是树形结构)。
并查集算法接口
并查集算法通常有以下几个接口:
判断两个元素p和q是否连通,即判断元素p和q是否拥有同一个根root,这里我们需要实现一个辅助函数find(int p),用于查找元素p的根。同理,将两个元素连通,只需要保证两个元素的根是同一个元素即可。
并查集算法代码
代码实现中,我们使用一个int型的数组parent来表示每一个元素的前驱元素是谁,即它的父节点是谁。如果将元素p和q连接起来了,可以说p是q的父节点,因此parent[q] = p。此时函数find(q)的结果也就是p了,也就是说,此时去寻找q元素的根节点,也就是p了。当然,也有可能p并不是根节点,因为p的根节点可能是m,即find(p)=m。所以find(q)的最终结果是m。(可以看到这里有迭代关系)。
下列是并查集算法的C++实现:
class UnionFind{
private:
// 元素个数
int n;
// 每个元素的父节点
int* parent;
// 连通分量个数
int ccount;
public:
UnionFind(int n){
this->n = n;
// 初始时,每个元素都独立,所以有n个连通分量
ccount = n;
this->parent = new int[n];
// 初始化每个元素的根节点是自己
for (int i = 0; i < n; i++){
parent[i] = i;
}
}
~UnionFind(){
// 注意释放空间
delete[]parent;
}
// 查找元素p的根
int find(int p){
while (p != parent[p]){
p = parent[p];
}
return p;
}
// 判断两个元素是否连通,即是否具有同一个根
bool connected(int p, int q){
return find(p) == find(q);
}
// 将两个元素连通
void unionElement(int p, int q){
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ)return;
parent[rootQ] = rootP;
// 连通后,连通分量将减少1
ccount--;
}
// 返回连通分量个数
int count(){
return ccount;
}
};
可以看到,并查集这个高级的数据结构,其实代码实现很简单。不过,这部分代码有优化的空间,比如查找函数中,可以使用路径压缩。
路径压缩
假设有如下一个连通图,我们要查找元素7的根,最终要经过6次迭代查找,这样的查找效率是很低的(类似于退化为链表的二叉树)。
我们可以做一些优化:如果经过一次查找发现7的根并不是7,那么可以将7的父节点指向其父节点的父节点,如下图:
这样只需要经过3次迭代就可以找到最终的root了。这就是路径压缩。
路径压缩的代码如下:
// 查找元素p的根:路径压缩
int find(int p){
while (p != parent[p]){
parent[p] = parent[parent[p];
p = parent[p];
}
return p;
}
求解朋友圈问题
再看看本文刚开始时提到的朋友圈问题,从示例给出的矩阵可以看到,这是一个对称矩阵,因此我们可以只考察左下或右上部分即可。如何考察呢?如果某个元素M[i][j]==1,说明i和j是好友,这时候只需要使用union将二者连接起来即可。
该题目求最后有几个朋友圈,其实也就是求有几个连通分量。由并查集的上述代码实现可知,初始化时,连通分量个数被初始化为元素个数,每当成功执行一次合并操作后,连通分量个数减1。所以最后我们直接返回count函数即可。
int findCircleNum(vector<vector<int>>& M) {
int num = M.size();
UnionFind uf(num);
for(int i=0;i<num;i++){
for(int j = i+1;j<num;j++){
if(M[i][j] == 1 && !uf.connected(i,j)){
uf.unionElement(i,j);
}
}
}
return uf.count();
}
更多关于并查集的题目和应用
LeetCode上还有更多可以使用并查集来求解的题目。比如:
并查集在图论中还有更强大的应用,使用并查集可以高效地判断图中是否有环,计算一个图的连通分量等等。比如我们一开始提到的Kruskal算法。Kruskal算法是用于求解最小生成树问题的一个经典算法。(关于最小生成树和Kruskal算法,之后再细说)。这里说下,Kruskal算法中是如何利用并查集来判断图中是否有环的?
比如下图的例子,在这样一个图中,如果我们把8和2进行union操作,将会形成一个环8-9-6-2-8。根据Kruskal算法,最小生成树中是不能有环的。如何判断呢?
如果find(2)和find(8)得到的是同一个root,上图的root是10,那说明其实2和8已经连通了,如果再次连通,必将形成一个环。这个判断过程其实就是并查集的接口connect的实现过程:
// 声明一个对象
UnionFind uf(n);
// Do something
// 判断p和q是否已经连通
if (uf.connected(p, q){
// 已经连通,则返回
return;
}
// 如果没有连通,则将两个元素连通
uf.unionElements(p, q);
// Do something
怎么样,并查集是不是很神奇?