并查集及代码实现

文章目录

1. 并查集1.1 并查集的概念1.2 并查集的实现思路1.3 代码

1. 并查集

1.1 并查集的概念

并查集也是一种数据结构，主要有两个操作，集合的合并，判断两个元素是否属于同一个集合，是一种逻辑结构。

1.2 并查集的实现思路

并查集的底层实现有多重方式，可以使用数组、List、树等等，选择的依据是哪种实现方式可以让操作的复杂度小。可以使用一种特殊的树来实现并查集如图，每一个结点都有一个父结点，最后一个结点的父节点指向自己，也是这个集合的代表结点，判断两个元素是否属于同一个集合，就是判断这两个元素所在集合的代表结点是否相等，合并两个集合，让结点数少的集合，挂载结点数多的代表结点的下面。 具体实现时，可以使用Map，使操作更简单。

1.3 代码

public class Code_09_UnionFind { public static class Node{ // whatever you like } public static class DisjointSets{ //定义两个Map,fatherMap<Node, fatherNode>, 存储结点和他的父节点，sizeMap<Node, Integer> //存储结点和以这个结点为父节点的结点个数，并且，只有当这个结点是代表结点的时候，sizeMap中的 //value值才有意义 public Map<Node, Node> fatherMap; public Map<Node, Integer> sizeMap; public DisjointSets(List<Node> list){ fatherMap = new HashMap<>(); sizeMap = new HashMap<>(); makeSets(list); } //初始化并查集，使用并查集的条件是，必须要知道所有元素 //开始的时候，每个结点的父节点都是自己。 public void makeSets(List<Node> list){ fatherMap.clear(); sizeMap.clear(); for(Node node : list){ fatherMap.put(node, node); sizeMap.put(node, 1); } } //根据一个元素，查找这个元素所在的集合的代表结点，并且，将这个集合压缩，就是从这个结点 //到代表结点之间的所有节点的父节点，都指向代表结点 public Node findFather(Node node){ Node father = fatherMap.get(node); if(father != node){ //这里使用的是递归，如果node的父节点不是father，就找父节点的父节点，直到找到 //代表结点，node是一直在变的 father = findFather(father); } //找到代表结点之后，将每个结点的父节点设为代表结点 fatherMap.put(node, father); //返回father return father; } //判断两个元素是否属于同一个集合 public boolean isSameSet(Node node1, Node node2){ return findFather(node1) == findFather(node2); } //合并两个集合 public void union(Node a, Node b){ if(a == null || b == null) return; Node aFather = findFather(a); Node bFather = findFather(b); if(aFather != bFather){ int aFatherSize = sizeMap.get(aFather); int bFatherSize = sizeMap.get(bFather); if( aFatherSize <= bFatherSize){ //如果a所在集合结点数少于b的，就将a的父节点设为b的父节点，a挂载b后头 fatherMap.put(aFather, bFather); //修改个数 sizeMap.put(bFather, aFatherSize + bFatherSize); }else{ fatherMap.put(bFather, aFather); sizeMap.put(aFather, aFatherSize + bFatherSize); } } } } }

时间复杂度：假设有n个元素，如果查询的次数（查找代表结点）加上合并的次数的数量级达到或者超过了O(n)，那么，单次查询或者单次合并，平均复杂度为O(1)。证明过程很复杂，略。

如有不足之处，欢迎指正，谢谢！