并查集UFS
简介
并查集(Union Find Set)是一种高级数据结构，主要用于图存储中不同集合的合并与查询问题。并查集这种数据结构在数据存储时，由于使用了路径压缩的方法，使得最终的查询时间复杂度大大降低，变成了O(1)
实现思路
并查集归根结底可以算作是树形结构，主要实现了两个功能，union和find
假设有["A","B","C","D","E","F"]6个节点，其中("A","E"),("B","C"),("C","F")两两关联。那么最终会得到3个集合(D)、(A,E)和(B,C,F)
如下图：
分别对A,B,C,D,E,F标号为1,2,3,4,5,6。因为A,E相连，把A和E的索引（也有叫做父节点的）换成相同的。因为B,C,F相连，把B,C,F的索引换成相同的，如下图：
得到这个结果后，能够知道A,B,C,D,E,F共有3个连通集合，分别是1,2,3。此过程在创建并查集的时候（也可以是首次查找时）实现，存储了这样的数据结构后，在查找F时可以直接找到F属于簇2，而不需要找F的父节点是C，C的父节点是B。
Python代码实现
class UnionFindSet(object):
parent = []# 存储每个元素的父节点，记作1,2,3,4,5...
count =0 # 一共有几组，初始化时各元素单独成组
def __init__(self, origin_set, n):
self.count = n# 样本数量
self.partition_count = n# 样本分类数量
self.origin_items = origin_set# 样本们
# 初始化的数据结构时，每个元素的父节点都是自己,然后做union
for i in range(0, n):
self.parent.append(i)
def isconnect(self, i, j):
return self.find(i) == self.find(j)
def find(self, i):
p_i = self.origin_items.index(i)
return self.parent[p_i]
def find_set(self, cluster):
result = []
size = len(self.parent)
for indexin range(size):
if self.parent[index] == cluster:
result.append(self.origin_items[index])
return result
def union(self, i, j):
root_i = self.find(i)
root_j = self.find(j)
if root_i == root_j:
print ("----------%s 和 %s 已经是连通的----------" %(i, j))
return True
else:# root_i != root_j:
self.parent[root_i] = root_j
self.partition_count -=1
for xin self.origin_items:
# 如果父节点相同,压缩路径
if self.parent[self.origin_items.index(x)] == root_i:
self.parent[self.origin_items.index(x)] = root_j
def main():
sample = ["A","B","C","D","E","F"]
sample_n = len(sample)
ufs = UnionFindSet(sample, sample_n)
print ("初始化并查集parent list: %s" % (",").join(str(x)for xin ufs.parent))
link = [
("A","E"),
("B","C"),
("C","F")
]
for k in link:
p = k[0]
q = k[1]
ufs.union(p, q)
print ("建立连接关系: %s和%s " %(p, q))
print ("最终分类数量: %s" %(ufs.partition_count))
print ("最终分类:\n %s\n%s" %(sample, ufs.parent))
item ="A"
cluster = ufs.find(item)
print ("%s属于%s" %(item, cluster))
最后在网上找到一张有意思的图，能够清晰的说明并查集是什么。门派的划分！
代码是描绘客观事物存在方式和运动方式的一组计算机符号啊
