并查集路径压缩
如何描述一个复杂的连接关系？如图，很容易判断紧邻的2个人关系，但中间的连接很多很乱，怎么判断出两个人的关系呢？ 并查集就是一种结构，通过保存节点以及节点上的标签，来判断这两个节点是否连接在一起。当两个节点绑定时，可以任选其中一个节点的标签，指定另一个节点。当判断两个节点是不是连接时，可以上溯节点的祖宗节点，如果祖宗节点相同，那么节点相连。此时，节点上的标签可理解为指向父亲节点。
并查集的并&查
1.节点列表
并查集中的节点只需要保存父亲节点的信息，那么线性结构字典、列表都可以。我们用一维数组，索引是自身id，值指向父亲。 初始化时每个节点指向自身。
class UnionFind:
def __init__(self,size):
self.size = size
self.parent = np.arange(size)
def union(self,p,q): ##将两个节点连接在一起
def isConnected(self,p,q): ## 判断两个节点是否相连2.判断两个节点相连
当两个节点的祖宗节点相同时，两个节点就是连接节点。
def find(self,p):
assert p>=0 and p<self.size
while (self.parent[p]!=p):
##向上遍历，当父节点不是自己时，
##那么还存在父节点，继续遍历。
p = self.parent[p]
return p
def isConnected(self,p,q):
##当祖宗节点相同时，两个节点是连接节点
return self.find(p)==self.find(q)3.节点连接
当节点连接时，需要将2个节点的祖宗节点相连，可任选一个节点连接另一个节点。
def union(self,p,q):
pRoot = self.find(p)
qRoot = self.find(q)
if pRoot == qRoot:
return
else:
## 第一个节点祖宗节点指向第二节点的祖宗节点
self.parent[pRoot] = qRoot4.优化连接
第3小节，我们任意选择一个节点连接，这样的选择有问题。举例：一层和二层节点集合合并：
- 如果二层节点的祖宗节点连接到一层节点上，那么就形成了一个三层节点集。
- 另一种可能，一层节点连接到二层祖宗节点，新集还是二层。
层数越少，查询祖宗节点的代价越小，应让节点层数少的连接到层数高的。
class UnionFind:
def __init__(self,size):
self.size = size
self.parent = np.arange(size)
self.rank = np.ones(size) //记录该节点下面的层次，默认都是1层
def unionByRank(self,p,q):
assert p>=0 and p<self.size and q>=0 and q<self.size
pRoot = self.find(p)
qRoot = self.find(q)
if pRoot == qRoot:
return self
else:
## rank小的，添加到rank大的，这样的合并不增加rank。rank节点向上遍历的步数。
if(self.rank[pRoot] > self.rank[qRoot]):
self.parent[qRoot] = pRoot
elif(self.rank[qRoot] > self.rank[pRoot]):
self.parent[pRoot] = qRoot
else:
self.parent[pRoot] = qRoot
self.rank[qRoot] +=1
return self5.路径压缩
进一步优化，使每个节点直接指向它的祖宗节点。
def findCompress2(self,p):
if p!=self.parent(p):
self.parent[p] = self.findCompress2(self.parent[p])
return self.parent[p]通过递归调用，函数从某一点出发，上溯到祖宗节点，返回值传递祖宗节点。函数返回时，相当于祖宗节点向下遍历，对每一个节点父节点重新赋值。
总结：
本文两个重点：介绍了并查集和路径压缩；单向列表的反向遍历。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2018.08.24 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
腾讯云开发者
