应用范围:
一开始我有n个集合,这个集合可以先理解为数学上的集合,每个节点都首先自成一个集合,n个节点就相当于有n个集合。并查集支持的操作:你想查两个节点是否来自同一个集合,或者想合并两个集合
前提:
每个节点必须先自成一个集合,所有点必须建立一个集合
优点:
如果你有n个节点,你想查两个节点是否来自于一个集合的操作数(操作发生的次数),例如你想查两个节点是否来自于一个集合的操作次数是k,集合合并的次数为f,并且k(次数)+f(次数)是O(n),并查集的操作次数是O(n),平均查询和合并的时间复杂度为O(1)
递归过程解析
image.png
代码:
public static class Node {
// whatever you like
}
public static class DisjointSets {
public HashMap<Node, Node> fatherMap;
public HashMap<Node, Integer> rankMap;
public DisjointSets() {
fatherMap = new HashMap<Node, Node>();
rankMap = new HashMap<Node, Integer>();
}
public void makeSets(List<Node> nodes) {
fatherMap.clear();
rankMap.clear();
for (Node node : nodes) {
fatherMap.put(node, node);
rankMap.put(node, 1);
}
}
public Node findFather(Node n) {
Node father = fatherMap.get(n);
if (father != n) {
father = findFather(father);
}
fatherMap.put(n, father);
return father;
}
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 aFrank = rankMap.get(aFather);
int bFrank = rankMap.get(bFather);
if (aFrank <= bFrank) {
fatherMap.put(aFather, bFather);
rankMap.put(bFather, aFrank + bFrank);
} else {
fatherMap.put(bFather, aFather);
rankMap.put(aFather, aFrank + bFrank);
}
}
}
}
网友评论