前言
前几天想把并查集这个结构搞清楚，但一直没有动笔写。
因为要有输出，印象才会更深刻些。
这里只是非常简单的记录一下。
并查集
并查集，顾名思义，最主要的2大功能就是并（合并），查（查找）。
合并 ： 将2个不在同一个集合内的元素 所在的集合 合并在同一个集合。
查找 ： 看看2个元素是否在 同一个集合内。
但是在 新建一个这个结构的时候，就必须把全部元素拿给他，也就是说，这种结构只能处理事先已经知道全部元素是什么的情况，不能一个一个的元素给他，不能处理 “流” 这种情况。
主要功能实现
- 初始化 ： 在给了所有元素之后，各自元素单独成一个集合，也就是自己指向自己，自己的父节点是自己。自己所在的集合的代表节点就是自己。
- 找最头的那个节点，就是找一个集合的代表节点： 递归下去，有优化途径，就是在找的时候，以后的每个“父节点”都指向这个集合的代表节点（就是那个最终要找的节点）。也就是路径压缩，把长链给打扁平了，方便后续的查找操作，要不然的话性能会慢些许。
- 合并： 将2个元素的所在的集合合并成一个集合，以后再查的时候，这2个集合里的所有元素都是在一起的。在合并的时候，为性能优化，就把集合里元素少的那个集合的代表节点 指向 集合里元素多的那个集合的代表节点。
代码：
// 取一个类Node只是方便后续代码实现， 具体这个Node类里是什么都可以
public static class Node{
int i;
public Node(int i) {
this.i = i;
}
}
public static class UnionFind {
private HashMap<Node, Node> fatherMap; // key 是当前节点； value 是当前节点的 父亲，一直往上找，即这个集合的代表节点
private HashMap<Node, Integer> sizeMap; // 这个节点所在的集合的节点个数有多少
public UnionFind(List<Node> nodes) {
makeSet(nodes);
}
private void makeSet(List<Node> nodes) {
fatherMap = new HashMap<Node, Node>();
sizeMap = new HashMap<Node, Integer>();
for(Node n : nodes) {
fatherMap.put(n, n);
sizeMap.put(n, 1);
}
}
private Node findFather(Node node) {
Node father = fatherMap.get(node);
if(father != node) {
father = fatherMap.get(father);
}
fatherMap.put(node, father);
return father;
}
public boolean isSameSet(Node a, Node b) {
return findFather(a) == findFather(b);
}
public void union(Node a, Node b) {
if(a == null || b == null) {
return;
}
Node aHead = findFather(a);
Node bHead = findFather(b);
if(aHead == bHead) {
return;
}
int aSetSize = sizeMap.get(aHead);
int bSetSize = sizeMap.get(bHead);
if(aSetSize <= bSetSize) {
fatherMap.put(aHead, bHead);
sizeMap.put(bHead, aSetSize+bSetSize);
} else {
fatherMap.put(bHead, aHead);
sizeMap.put(aHead, aSetSize+bSetSize);
}
}
}
京公网安备 11010502036488号