Java实现并查集

Java实现并查集

本文实例为大家分享了java实现并查集的具体代码，供大家参考，具体内容如下

自下而上的树结构

接口

/**

* @author NiRBaKbMGno

*/

public interface UF {

int size();

/**

* 看两个元素是否相连

* @param p

* @param q

* @return

*/

boolean isConnected(int p, int q);

/**

* 将两个元素合并在一起，变成一个集合中的元素

* @param p

* @param q

*/

void unionElements(int p, int q);

}

使用路径压缩的并查集

/**

* @author Nino

*/

public class UnionFind5 implements UF {

private int[] parent;

//rank[i]表示以i为根的集合中树的层数

private int[] rank;

public UnionFind5(int size) {

parent = new int[size];

rank = new int[size];

for (int i = 0; i < size; i++) {

parent[i] = i;

rank[i] = 1;

}

}

@Override

public int size() {

return parent.length;

}

/**

* 查找过程，查找元素p所对应的集合编号

* O(h)复杂度，h为树的高度

* 使用路径压缩

* @param p

* @return

*/

private int find(int p) {

if (p < 0 && p >= parent.length) {

throw new IllegalArgumentException("p is illegal");

}

if (p != parent[p]) {

parent[p] = find(parent[p]);

}

return parent[p];

}

/**

* 查询p, q是否同属一个集合

* 时间复杂度O(h)

* @param p

* @param q

* @return

*/

@Override

public boolean isConnected(int p, int q) {

return find(p) == find(q);

}

/**

* 合并元素p, q所属的集合，只需要把Rank低的根节点指向Rank高的根节点就可以

* O(h)复杂度

* @param p

* @param q

*/

@Override

public void unionEhttp://lements(int p, int q) {

int pRoot = find(p);

int qRoot = find(q);

if (pRoot == qRoot) {

return;

}

//败者食尘

if (rank[pRoot] < rank[qRoot]) {

parent[pRoot] = qRoot;

} else if (rank[qRoot] < rank[pRoot]) {

parent[qRoot] = pRoot;

} else {

parent[qRoot] = pRoot;

rank[pRoot] += 1;

}

}

}