Union Find并查集

收藏到CSDN网摘


union find并查集是数据结构与算法问题中经常碰到的典型数据结构,作为二十世纪最伟大的十个算法之一(不知道是谁评的),在很多问题中都有非常独到的应用.例如判断某2个点是否连通(迷宫路径问题).普林斯顿的在线课程数据结构与算法第一章讲的就是它,而且由浅入深,逐步实现了有一个普通的实现到最后的加权优化实现以极大压缩生成树的高度来实现高效判断.下面是python实现的代码:

class uf(object):
    ''' weighted union find object '''
    def __init__(self,n):
        self.id = range(n)  # root
        self.sz = [1]*n     # size of its children

    def count(self):
        # return the number of components
        return len(set(self.id))

    def connected(self,p,q):
        # check if 2 cells are connected
        return self.find(p)==self.find(q)
    
    def find(self,p):
        # get the root of current cell
        while p!=self.id[p]:
            self.id[p] = self.id[self.id[p]]
            p = self.id[p]
        return p

    def union(self,p,q):
        # union 2 cells
        pid,qid = self.find(p),self.find(q)
        if pid==qid: return
        # join the smaller tree to the bigger
        if self.sz[pid]<self.sz[qid]:
            self.id[pid] = qid
            self.sz[qid] += self.sz[pid]
        else:
            self.id[qid] = pid
            self.sz[pid] += self.sz[qid]