Disjoint Set Data Structure

不相交集合数据结构

概念: A disjoint-set data structure maintains a collection $S = \{ S_1; S_2; ... ; S_k \}$ of disjoint dynamic sets. We identify each set by a representative, which is some member of the set.

---

确定无向图的连通分量

有图 $Graph=G(V, E)$

MAKE-SET(e): 新建一个集合，包含e元素。

UNION($S_1$, $S_2$): 将集合$S_1$、$S_2$求并集，形成新的集合。

FIND-SET(e): 返回包含元素 e 的集合。

ConnectedComponents(G) 
    for each vertex(v) in G.V   
        MAKE-SET(v)  //init

    for each edge(u, v) in G.E   
        if $FIND-SET(u) != FIND-SET(v)  
            UNION(u, v)  


SameComponent(u, v)  
    if $FIND-SET(u) == $FIND-SET(v)  
        return true  
    else return false  

利用此算法可确认或划分出连通子图。

---

参考

[1] Thomars H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introduction to Algorithms.