简介

并查集(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))

---

最后在网上找到一张有意思的图，能够清晰的说明并查集是什么。门派的划分！

代码是描绘客观事物存在方式和运动方式的一组计算机符号啊