并查集路径压缩

如何描述一个复杂的连接关系？如图，很容易判断紧邻的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] = qRoot

4.优化连接

第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 self

5.路径压缩

进一步优化，使每个节点直接指向它的祖宗节点。

    def findCompress2(self,p):
        if p!=self.parent(p):
            self.parent[p] = self.findCompress2(self.parent[p])           
        return self.parent[p]

通过递归调用，函数从某一点出发，上溯到祖宗节点，返回值传递祖宗节点。函数返回时，相当于祖宗节点向下遍历，对每一个节点父节点重新赋值。

总结：

本文两个重点：介绍了并查集和路径压缩；单向列表的反向遍历。