首页 > 代码库 > 《数据结构与算法分析:C语言描述》复习——第八章“并查集”——并查集
《数据结构与算法分析:C语言描述》复习——第八章“并查集”——并查集
2014.06.18 14:16
简介:
“并查集”,英文名为“union-find set”,从名字就能看出来它支持合并与查找功能。另外还有一个名字叫“disjoint set”,中文名叫不相交集合。可能我们倾向于用最短的名字,所以就出现了“并查集”翻译为“disjoint set”的情况。并查集是一种树形结构,但与之前讲的树不同的是,这里的树节点只记录父节点,因此是一对一的,就可以用数组来表示并查集。
图示:
并查集可以认为是一个“森林”,也就是多棵树:
既然是并查集,先看看合并3和5之后结果如何:
那么3和5岂不是父子关系了?不是。我们关心的不是谁是父谁是子,而是3和5现在在一起了。下面这样效果是一样的:
这个看起来不像树形结构啊?那就来个节点个数更多的例子:
再看看查找操作:
这样的查找操作不改变树的形状,自底向上,复杂度必然是O(H),也就是和树的高度成正比。有什么坏处呢?
路径压缩可以通过让树变得更扁来降低高度,从而加速查找操作。首先仍然是查找:
然后依次把沿路的所有节点直接挂到根节点上:
图片占的篇幅更少,显然是因为树变矮了。现在查找操作只需要O(1)时间了。
那么并查集有什么用呢?通俗地说,是用来判断一群人中,谁和谁是一伙儿的,谁和谁不是。不通俗地说,可以看看“等价关系”、“等价类”的一些集合论的资料,从中寻找一些理论支持。
在此给出一道用并查集解决的ZOJ简单题:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2833
实现:
1 // My implementation for disjoint set. 2 #include <vector> 3 using namespace std; 4 5 int findRoot(const vector<int> &dj, int x) 6 { 7 int k, r; 8 9 r = x;10 while (r != dj[r]) {11 r = dj[r];12 }13 14 k = x;15 while (k != r) {16 x = dj[x];17 dj[k] = r;18 k = x;19 }20 21 return r;22 }23 24 void unionSet(vector<int> &dj, int x, int y)25 {26 int n = (int)dj.size();27 28 if (x == y) {29 return;30 }31 32 dj[x] = y;33 findRoot(x);34 }35 36 int main()37 {38 return 0;39 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。