WiKi

Disjoint是“不相交”的意思。Disjoint Set高效地支持集合的合并（Union）和集合内元素的查找（Find）两种操作，所以Disjoint Set中文翻译为并查集。

就《算法导论》21章来讲，主要设计这几个知识点：

 用并查集计算图的连通区域；

 推断两个顶点是否属于同一个连通区域；

 链表实现并查集；

 Rooted tree实现并查集；

 Rooted tree实现并查集时採用rank方法和路径压缩算法。

《算法导论》21.4给出了一个结论：总计m个MAKE-SET、UNION、FIND-SET操作。当中MAKE-SET的个数为n，则採用rank和路径压缩算法实现的并查集最坏时间复杂度是O(m α(n) )。当中α是Ackerman函数的某个反函数，这个函数的值能够看成是不大于4。所以，并查集的三种典型操作的时间复杂度是线性的。

相关资料

并查集的维基百科

并查集的java实现

这里依据《算法导论》的21.3节的伪代码，实现了一个泛型的并查集。输出时，打印节点及其集合的代表元素（即根元素。representative）。

import java.util.ArrayList;

import java.util.List;

import java.util.TreeSet;

/**

 * <p>并查集的实现<p/>

 * <p>參考：《算法导论》21.3节<p/>

 * <p>created by 曹艳丰<p/>

 * <p>2016-08-31<p/>

 *

 * */

public class DisjointSet<T> {

    private List<Node> forests;//全部节点

    public DisjointSet(){

        forests=new ArrayList<Node>();

    }

    /**

     * 内部类，并查集的rooted node

     * */

    private class Node{

        Node parent;

        int rank;

        T t;

        private Node(T t){

            parent=this;

            rank=0;

            this.t=t;

        }

    }

    //向森林中加入节点

    public void makeSet(T t){

        Node node=new Node(t);

        forests.add(node);

    }

    //将包括x和包括y的两个集合进行合并

    public void union(T x,T y){

        Node xNode=isContain(x);

        Node yNode=isContain(y);

        if (xNode!=null&&yNode!=null) {

            link(findSet(xNode), findSet(yNode));

        }

    }

    //查找到节点node的根节点

    public Node findSet(Node node){

        if (node!=node.parent) {

            //路径压缩，參考《算法导论》插图21.5

            node.parent=findSet(node.parent);

        }

        return node.parent;

    }

    //查找到节点node的根节点

        public Node findSet(T t){

            Node node=isContain(t);

            if (node==null) {

                throw new IllegalArgumentException("不含该节点！

");

            }else {

                return findSet(node);

            }

        }

    //将两个根节点代表的集合进行连接

    private void link(Node xNode,Node yNode){

        if (xNode.rank>yNode.rank) {

            yNode.parent=xNode;

        }else {

            xNode.parent=yNode;

            if (xNode.rank==yNode.rank) {

                yNode.rank+=1;

            }

        }

    }

    //森林是否包括这个节点

    private Node isContain(T t){

        for (Node node : forests) {

            if (node.t.equals(t)) {

                return node;

            }

        }

        return null;

    }

    @Override

    public String toString() {

        // TODO Auto-generated method stub

        if (forests.size()==0) {

            return "并查集为空！";

        }

        StringBuilder builder=new StringBuilder();

        for (Node node : forests) {

            Node root=findSet(node);

            builder.append(node.t).append("→").append(root.t);

            builder.append("\n");

        }

        return builder.toString();

    }

}

然后測试一下

public class Main{

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        DisjointSet<String> disjointSet=new DisjointSet<String>();

        disjointSet.makeSet("cao");

        disjointSet.makeSet("yan");

        disjointSet.makeSet("feng");

        disjointSet.union("cao", "yan");

        disjointSet.union("cao", "feng");

        System.out.println(disjointSet.toString());

    }

}

输出格式，元素→代表元素

cao→yan

yan→yan

feng→yan

表明3个节点的代表元素一致。即处于一个集合中。

图的连通区域计算`

《算法导论》21.1节的伪代码。这里给出连通区域计算的样例。图的数据结构採用“【算法导论-35】图算法JGraphT开源库介绍 “中的无向图。

private static void connectedComponents(){

        UndirectedGraph<String, DefaultEdge> g =

                new SimpleGraph<>(DefaultEdge.class);

        String v1 = "v1";

        String v2 = "v2";

        String v3 = "v3";

        String v4 = "v4";

        // add the vertices

        g.addVertex(v1);

        g.addVertex(v2);

        g.addVertex(v3);

        g.addVertex(v4);

        // add edges to create a circuit

        g.addEdge(v1, v2);

        g.addEdge(v2, v3);

        //连通区域计算

        //參考《算法导论》21.1节

        DisjointSet<String> disjointSet=new DisjointSet<String>();

        for ( String v : g.vertexSet()) {

            disjointSet.makeSet(v);

        }

//        for ( DefaultEdge e : g.edgeSet()) {

//          String source=e.getSource();//protected訪问类型

//          String target=e.getTarget();//protected訪问类型

//          if (disjointSet.findSet(source)!=disjointSet.findSet(target)) {

//              disjointSet.union(source, target);

//          }

//      }

        if (disjointSet.findSet(v1)!=disjointSet.findSet(v2)) {

            disjointSet.union(v1, v2);

        }

        if (disjointSet.findSet(v2)!=disjointSet.findSet(v3)) {

            disjointSet.union(v2, v3);

        }

        System.out.println(disjointSet.getSetCounter());

    }

输出

v1→v2

v2→v2

v3→v2

v4→v4

v1、v2、v3的代表元素一致。表明三者在一个集合中，即三者连通。

v4是另外一个集合。

实例应用

举个样例，某人结婚时宴请宾客，A来宾认识B来宾，B来宾认识C来宾，则A、B、C安排在一桌。

A来宾认识B来宾，且A、B的熟人及其熟人的熟人（熟人链）不包括C，则C与A、B不在一桌。问。须要多少桌子才干满足要求呢？

这个样例事实上就是连通区域的详细到社交关系的1度、2度……n度关系。

略微改动并查集的实例，加入集合的计数setCounter，每次makeset时递增，union时递减。这样就得到最后的集合个数。

import java.util.ArrayList;

import java.util.List;

import java.util.TreeSet;

/**

 * <p>并查集的实现<p/>

 * <p>參考：《算法导论》21.3节<p/>

 * <p>created by 曹艳丰<p/>

 * <p>2016-08-31<p/>

 *

 * */

public class DisjointSet<T> {

    private List<Node> forests;//全部节点

    private int setCounter;//集合计数

    public DisjointSet(){

        forests=new ArrayList<Node>();

        setCounter=0;

    }

    public int getSetCounter() {

        return setCounter;

    }

    /**

     * 内部类，并查集的rooted node

     * */

    private class Node{

        Node parent;

        int rank;

        T t;

        private Node(T t){

            parent=this;

            rank=0;

            this.t=t;

        }

    }

    //向森林中加入节点

    public void makeSet(T t){

        Node node=new Node(t);

        forests.add(node);

        setCounter++;

    }

    //将包括x和包括y的两个集合进行合并

    public void union(T x,T y){

        if (x.equals(y)) {

            throw new IllegalArgumentException("Union的两个元素不能相等。");

        }

        Node xNode=isContain(x);

        Node yNode=isContain(y);

        if (xNode!=null&&yNode!=null) {

            link(findSet(xNode), findSet(yNode));

            setCounter--;

        }

    }

    //查找到节点node的根节点

    public Node findSet(Node node){

        if (node!=node.parent) {

            //路径压缩，參考《算法导论》插图21.5

            node.parent=findSet(node.parent);

        }

        return node.parent;

    }

    //查找到节点node的根节点

        public Node findSet(T t){

            Node node=isContain(t);

            if (node==null) {

                throw new IllegalArgumentException("不含该节点！

");

            }else {

                return findSet(node);

            }

        }

    //将两个根节点代表的集合进行连接

    private void link(Node xNode,Node yNode){

        if (xNode.rank>yNode.rank) {

            yNode.parent=xNode;

        }else {

            xNode.parent=yNode;

            if (xNode.rank==yNode.rank) {

                yNode.rank+=1;

            }

        }

    }

    //森林是否包括这个节点

    private Node isContain(T t){

        for (Node node : forests) {

            if (node.t.equals(t)) {

                return node;

            }

        }

        return null;

    }

    @Override

    public String toString() {

        // TODO Auto-generated method stub

        if (forests.size()==0) {

            return "并查集为空！";

        }

        StringBuilder builder=new StringBuilder();

        for (Node node : forests) {

            Node root=findSet(node);

            builder.append(node.t).append("→").append(root.t);

            builder.append("\n");

        }

        return builder.toString();

    }

}

连通区域的计算，只是这里输出的是集合个数。

private static void connectedComponents(){

        UndirectedGraph<String, DefaultEdge> g =

                new SimpleGraph<>(DefaultEdge.class);

        String v1 = "v1";

        String v2 = "v2";

        String v3 = "v3";

        String v4 = "v4";

        // add the vertices

        g.addVertex(v1);

        g.addVertex(v2);

        g.addVertex(v3);

        g.addVertex(v4);

        // add edges to create a circuit

        g.addEdge(v1, v2);

        g.addEdge(v2, v3);

        //连通区域计算

        //參考《算法导论》21.1节

        DisjointSet<String> disjointSet=new DisjointSet<String>();

        for ( String v : g.vertexSet()) {

            disjointSet.makeSet(v);

        }

//        for ( DefaultEdge e : g.edgeSet()) {

//          String source=e.getSource();//protected訪问类型

//          String target=e.getTarget();//protected訪问类型

//          if (disjointSet.findSet(source)!=disjointSet.findSet(target)) {

//              disjointSet.union(source, target);

//          }

//      }

        if (disjointSet.findSet(v1)!=disjointSet.findSet(v2)) {

            disjointSet.union(v1, v2);

        }

        if (disjointSet.findSet(v2)!=disjointSet.findSet(v3)) {

            disjointSet.union(v2, v3);

        }

        System.out.println(disjointSet.getSetCounter());

    }

输出是2。