基本概念

  并查集Disjoint Set可能是最简单的数据结构了。它的用途不是很广，主要用于最小生成树的Kruskal算法、Boruvka算法、图的查环等。并查集这个中文翻译不是很恰当，Disjoint Set，在数学上是没有共同元素的集合。在数据结构中是指互相没有公共元素的一群集合，并且要支持创建、合并、查找三种操作。
  从抽象定义上看，没有要求用森林实现。但是为了性能等方面考虑，最好是用森林实现。合并时，是一棵树成为另一棵树的parent节点。为了树的平衡，减少树查询层数，用一个rank字段来记录层数，并且按照层数来合并。搜索使用递归方法。
  并查集Disjoint Set是一个森林，包含了很多棵树，每棵树叫Handler。

基本操作

  创建make set，指的是传入一个元素，返回一个只含一个元素的并查集。
  查找find set，传入元素，返回包含该元素的并查集。
  合并union set，将两个集合合并。
  路径压缩path compression technique，在查找时，将指向parent的长链缩短成两级，方便以后再次查询。

Java实现

因为逻辑比较简单，所以就直接贴java代码了。代码中包含了测试方法。

public class DisjointSet<T> {
    private T value;
    private DisjointSet<T> parent;
    private int rank;

    public DisjointSet(T value) {
        this.value = value;
        parent = this;
    }

    public void union(DisjointSet<T> other) {
        this.link(other);
    }

    private void link(DisjointSet<T> other) {
        if (this.rank > other.rank) {
            other.parent = this;
        } else {
            this.parent = other;
            if (this.rank == other.rank) {
                other.rank = this.rank + 1;
            }
        }
    }

    public DisjointSet<T> findSet() {
        if (this != this.parent) {
            this.parent = parent.findSet();
        }
        return parent;
    }

    @Override
    public String toString() {
        return value.toString();
    }

    public static void main(String[] args) {
        final DisjointSet<Integer> set1 = new DisjointSet<>(3);
        final DisjointSet<Integer> set2 = new DisjointSet<>(5);
        final DisjointSet<Integer> set3 = new DisjointSet<>(7);
        set1.union(set2);
        System.out.println(set1.findSet());
        set1.union(set3);
        System.out.println(set2.findSet());
    }
}

Python实现

# 并查集
class Handler:

    def __init__(self, vertex):
        self.__vertex = vertex
        self.__parent = self
        self.__rank = 0

    @property
    def vertex(self):
        return self.__vertex

    @property
    def parent(self):
        return self.__parent

    @parent.setter
    def parent(self, value):
        self.__parent = value

    @property
    def rank(self):
        return self.__rank

    @rank.setter
    def rank(self, value):
        self.__rank = value

    def union(self, other):
        if self.__rank > other.__rank:
            other.__parent = self
        else:
            self.__parent = other
            if self.__rank == other.__rank:
                other.__rank = other.__rank + 1

    def find(self):
        x = self
        if x != x.__parent:
            x.__parent = x.parent.find()
        return x.__parent

class DisjointSet:
    # 对于每一个item，应该找到属于它的最小的集合

    def __init__(self, n):
        self.__forest = [None] * n

    def make_set(self, item):
        h = Handler(item)
        self.__forest[item] = h
        return h

    def union_set(self, x, y):
        self.find_set(x).union(self.find_set(y))

    def find_set(self, item):
        return self.__forest[item].find()