连接问题--网络中节点间的连接状态 节点、边--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;
}
}
时间分析：
unionEl方法册数测试：size=10000
方法\数量复杂度10001000010W100W1000W
QuickFindUFO(n)0.0197秒0.0880秒0.1199秒0.1688秒0.5216秒QuickUnionUFO(logn)0.0015秒0.0132秒0.7418秒7.0839秒----秒quickUnion2UFO(logn)0.0017秒0.0050秒0.0220秒0.0966秒0.6657秒
unionEl方法册数测试：size=100000
方法\数量复杂度10001000010W100W1000W
QuickFindUFO(n)0.0197秒0.0880秒0.1199秒0.1688秒10.0468秒QuickUnionUFO(logn)0.0015秒0.0132秒0.7418秒7.0839秒----秒quickUnion2UFO(logn)0.0017秒0.0050秒0.0220秒0.0966秒0.8478秒
unionEl方法册数测试：size=1000000
方法\数量复杂度10001000010W100W1000W
QuickFindUFO(n)0.6346秒5.3409秒----秒----秒----秒QuickUnionUFO(logn)0.0012秒0.0052秒0.0281秒----秒----秒quickUnion2UFO(logn)0.0013秒0.0062秒0.0304秒0.2186秒1.8915秒
unionEl方法册数测试：size=10000000
方法\数量复杂度10001000010W100W1000W
quickUnion2UFO(logn)0.0013秒0.0063秒0.0335秒0.1903秒2.5726秒quickUnion3UFO(logn)0.0016秒0.0060秒0.0323秒0.1932秒2.5327秒
后记、
1.声明：
[1]本文由张风捷特烈原创,各图均由本人亲自所画，转载请注明 [2]欢迎广大编程爱好者共同交流 [3]个人能力有限，如有不正之处欢迎大家批评指证，必定虚心改正 [4]你的喜欢与支持将是我最大的动力
2.连接传送门：
更多数据结构知识欢迎访问:图解数据结构 项目源码均在我的https://github.com/toly1994328/DS：欢迎star 张风捷特烈个人网站，编程笔记请访问：http://www.toly1994.com
3.联系我
QQ:1981462002 邮箱：1981462002@qq.com 微信：zdl1994328
4.欢迎关注我的微信公众号，最新精彩文章，及时送达：
公众号.jpg
转载于:https://www.cnblogs.com/toly-top/p/9781865.html
