并查集(java)

并查集(java)

给定两个元素,已知这个两个元素位于两个集合中,如何判断这两个元素是否处于同一集合中,如果不处于,则合并这两个元素位于的集合,要求时间复杂度尽可能小。

如何解这个问题呢,根据合并和查找这两个特点,我们很好相处两种java的集合类,一种是list,一种是set

如果采用list来做,如果想要查询这两个元素是否位于同一集合,则必须遍历这两个list中的一个,如果发现在元素a所集合中同样有元素b,才能判定这两个元素位于同一集合。

对于list,很显而易见,很好合并这两个集合,直接将两个链表链接起来就完成了。

对于set,情况就恰恰相反了。我们很容易就能查询这两个元素是否在同一集合中,时间复杂度也是O(1)。

但是如果我们要合并这个两个集合,这就复杂了。

所以我们如何同时做到,既能很快查询又能很快合并。

这时我们提出并查集结构。

在给定的一个集合中,所有的元素都指向第一个元素,而第一个元素指向自身,查询是否位于同一集合,我们直接查询元素的父节点是否为同一个元素(该元素指向自身),合并两个集合时,我们将集合的父元素合并。

这样就能轻松实现查询与合并。

值得注意的是,当我们在查询时,如果我们发现某个元素的父节点不是指向自身,我们继续向上找父节点,直至它指向自身。在这个过程以后,我们要将该链打扁平,即是将我们遍历的节点全部指向真正父节点。

具体实现代码如下:

import java.util.HashMap;
import java.util.List;

public class UnionFind {
    public static class Node{
        public int value;
        public Node(int data){
            this.value = data;
        }
    }

    public static class UnionFindSet{
        private HashMap fatherMap;
        private HashMap sizeMap;

        public UnionFindSet(List nodes){
            makeSet(nodes);
        }
        private void makeSet(List nodes){
            fatherMap = new HashMap();
            sizeMap = new HashMap();
            for(Node node : nodes){
                fatherMap.put(node,node);
                sizeMap.put(node,1);
            }
        }

        private Node findHead(Node node){
            Node father = fatherMap.get(node);
            while (father != node){
                father = findHead(father);
            }
            fatherMap.put(node,father);
            return father;
        }

        public boolean isSameSet(Node node1,Node node2){
            return findHead(node1) == findHead(node2);
        }

        public void union(Node node1,Node node2){
            if(node1 ==null && node2 == null){
                return;
            }
            Node head1 = findHead(node1);
            Node head2 = findHead(node2);
            if(head1 != head2){
                int size1 = sizeMap.get(head1);
                int size2 = sizeMap.get(head2);
                if(size1<=size2){
                    fatherMap.put(head1,head2);
                    sizeMap.put(head2,size1+size2);
                }else {
                    fatherMap.put(head2,head1);
                    sizeMap.put(head1,size1+size2);
                }
            }
        }


    }
}

你可能感兴趣的