并查集路徑壓縮

如何描述一個複雜的連接配接關系？如圖，很容易判斷緊鄰的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]
           

通過遞歸調用，函數從某一點出發，上溯到祖宗節點，傳回值傳遞祖宗節點。函數傳回時，相當于祖宗節點向下周遊，對每一個節點父節點重新指派。

總結：

本文兩個重點：介紹了并查集和路徑壓縮；單向清單的反向周遊。