连接问题--网络中节点间的连接状态 节点、边--isConnrcted(p,q) 集合的并集---union(p,q)
并查询连接.png
/**
* 作者:张风捷特烈
* 时间:2018/9/25 0025:11:09
* 邮箱:1981462002@qq.com
* 说明:并查集接口
*/
public interface IUF {
/**
* 查看p,q元素是否属于同一集合
*
* @param p p元素
* @param q q元素
* @return 是否属于同一集合
*/
boolean isConnected(int p,int q);
/**
* 联合p,q所在集合
* @param p p元素
* @param q q元素
*/
void unionEl(int p, int q);
/**
* 元素个数
* @return 元素个数
*/
int size();
}
/**
* 作者:张风捷特烈
* 时间:2018/9/25 0025:11:15
* 邮箱:1981462002@qq.com
* 说明:快速查询并查集
*/
public class QuickFindUF implements IUF {
private int[] id;
public QuickFindUF(int size) {
id = new int[size];
for (int i = 0; i < id.length; i++) {
id[i] = i;
}
}
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
@Override
public void unionEl(int p, int q) {
int pID = find(p);
int qID = find(q);
if (pID == qID) {
return;
}
for (int i = 0; i < id.length; i++) {
if (id[i] == pID) {
id[i] = qID;
}
}
}
/**
* 查找元素p所对应的集合编号
*
* @param p 元素
* @return p所对应的集合编号
*/
private int find(int p) {
if (p < 0 || p >= id.length) {
throw new IllegalArgumentException("p is out of bound.");
}
return id[p];
}
@Override
public int size() {
return id.length;
}
}
isConnected方法复杂度O(1) unionEl方法复杂度O(n)
/**
* 作者:张风捷特烈
* 时间:2018/9/25 0025:11:15
* 邮箱:1981462002@qq.com
* 说明:快速合并并查集
*/
public class QuickUnionUF implements IUF {
private int[] parent;
public QuickUnionUF(int size) {
parent = new int[size];
//每个节点都是一颗树
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
}
}
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
@Override
public void unionEl(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
parent[pRoot] = qRoot;
}
/**
* 查找元素p所对应的集合编号
*
* @param p 元素
* @return p所对应的集合编号
*/
private int find(int p) {
if (p < 0 || p >= parent.length) {
throw new IllegalArgumentException("p is out of bound.");
}
while (p != parent[p]) {
p = parent[p];
}
return p;
}
@Override
public int size() {
return parent.length;
}
}
基于树实现,isConnected和unionEl的复杂度O(logn),但有可能退化到O(n)
/**
* 作者:张风捷特烈
* 时间:2018/9/25 0025:11:15
* 邮箱:1981462002@qq.com
* 说明:快速合并并查集优化
*/
public class QuickUnion2UF implements IUF {
private int[] parent;
/**
* 以treeSize[i]为根的集合元素个数
*/
private int[] treeSize;
public QuickUnion2UF(int size) {
parent = new int[size];
treeSize = new int[size];
//每个节点都是一颗树
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
treeSize[i] = 1;
}
}
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
@Override
public void unionEl(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
if (treeSize[pRoot] < treeSize[qRoot]) {
parent[pRoot] = qRoot;
treeSize[qRoot] += treeSize[pRoot];
} else {
parent[qRoot] = pRoot;
treeSize[pRoot] += treeSize[qRoot];
}
}
/**
* 查找元素p所对应的集合编号
*
* @param p 元素
* @return p所对应的集合编号
*/
private int find(int p) {
if (p < 0 || p >= parent.length) {
throw new IllegalArgumentException("p is out of bound.");
}
while (p != parent[p]) {
p = parent[p];
}
return p;
}
@Override
public int size() {
return parent.length;
}
}
/**
* 作者:张风捷特烈
* 时间:2018/9/25 0025:11:15
* 邮箱:1981462002@qq.com
* 说明:快速合并并查集优化
*/
public class QuickUnion3UF implements IUF {
private int[] parent;
/**
* 以rank[i]为根的集合元素个数
*/
private int[] rank;
public QuickUnion3UF(int size) {
parent = new int[size];
rank = new int[size];
//每个节点都是一颗树
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
rank[i] = 1;
}
}
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
@Override
public void unionEl(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;
}
}
/**
* 查找元素p所对应的集合编号
*
* @param p 元素
* @return p所对应的集合编号
*/
private int find(int p) {
if (p < 0 || p >= parent.length) {
throw new IllegalArgumentException("p is out of bound.");
}
while (p != parent[p]) {
p = parent[p];
}
return p;
}
@Override
public int size() {
return parent.length;
}
}
方法\数量 | 复杂度 | 1000 | 10000 | 10W | 100W | 1000W |
---|---|---|---|---|---|---|
QuickFindUF | O(n) | 0.0197秒 | 0.0880秒 | 0.1199秒 | 0.1688秒 | 0.5216秒 |
QuickUnionUF | O(logn) | 0.0015秒 | 0.0132秒 | 0.7418秒 | 7.0839秒 | ----秒 |
quickUnion2UF | O(logn) | 0.0017秒 | 0.0050秒 | 0.0220秒 | 0.0966秒 | 0.6657秒 |
方法\数量 | 复杂度 | 1000 | 10000 | 10W | 100W | 1000W |
---|---|---|---|---|---|---|
QuickFindUF | O(n) | 0.0197秒 | 0.0880秒 | 0.1199秒 | 0.1688秒 | 10.0468秒 |
QuickUnionUF | O(logn) | 0.0015秒 | 0.0132秒 | 0.7418秒 | 7.0839秒 | ----秒 |
quickUnion2UF | O(logn) | 0.0017秒 | 0.0050秒 | 0.0220秒 | 0.0966秒 | 0.8478秒 |
方法\数量 | 复杂度 | 1000 | 10000 | 10W | 100W | 1000W |
---|---|---|---|---|---|---|
QuickFindUF | O(n) | 0.6346秒 | 5.3409秒 | ----秒 | ----秒 | ----秒 |
QuickUnionUF | O(logn) | 0.0012秒 | 0.0052秒 | 0.0281秒 | ----秒 | ----秒 |
quickUnion2UF | O(logn) | 0.0013秒 | 0.0062秒 | 0.0304秒 | 0.2186秒 | 1.8915秒 |
方法\数量 | 复杂度 | 1000 | 10000 | 10W | 100W | 1000W |
---|---|---|---|---|---|---|
quickUnion2UF | O(logn) | 0.0013秒 | 0.0063秒 | 0.0335秒 | 0.1903秒 | 2.5726秒 |
quickUnion3UF | O(logn) | 0.0016秒 | 0.0060秒 | 0.0323秒 | 0.1932秒 | 2.5327秒 |
[1]本文由张风捷特烈原创,各图均由本人亲自所画,转载请注明 [2]欢迎广大编程爱好者共同交流 [3]个人能力有限,如有不正之处欢迎大家批评指证,必定虚心改正 [4]你的喜欢与支持将是我最大的动力