正文
算法练习_图的连通性问题（JAVA）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
一.问题
1.问题描述：
有n个点（1...n），输入整数对（8，9），表示8，9点之间存在相互的连接关系。
动态连通性问题--编写一段程序过滤掉所以无意义的整数对，即为在不破坏图连通性的前提下，以最简单的方式表示图的连通性。2.实现方案：设计数据结构保存已经存在的整数对，并且用他们来判断新数对是否满足新相连关系。
3.实例应用：网络连接问题，电子触电设计，社交网络关系等等
二.解决
1.定义问题--设计api
| public class UF//(类名大写) | ||
| （构造方法） | UN(int N) | 初始化0-N个触点 |
| void | union(int p,int q) | 在两点之间建立连接 |
| int | find(int p) | 在触点集中找到p |
| boolean | connected(int p,int q) | 判断触点p，q是否相连 |
| int | count() | 连通分量的计数 |
2.方案设计
<一>两个变量
count--用于连通分量的计数&&id[]--数组下标表示连通分量
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
初始化时下标默认为自身下标
在输入连通关系后（3，4），（5，6）
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0 | 1 | 2 | 4 | 4 | 6 | 6 | 7 | 8 | 9 |
将所以id[3]相同的下标修改为id[4]
从而表示数组的相连关系
1.quick-find
public int find(int p){
return id[p];
}
//对两点进行连接
public void union(int p,int q){
int pid=find(p);
int qid=find(q);
if(pid==qid)return;//直接return用于方法的推出
for(int i=0;i<id.length;i++)
if(id[i]==pid)id[i]=qid;
count--;
}
每次union需要访问数组(N+3)到(2N+1)次
2.quick-union
private int find(int p){
while(p!=id[p]){//找出根结点
p=id[p];
}
return p;
}
private void union(int p,int q){
int prot=find(p);
int qrot=find(q);
if(qrot==prot)return;
id[qrot]=prot;
count--;
}
3.union-find算法，加权
public class UF {
private int[] id;
private int[] sz;
private int count;
//初始化
public UF(int N){
count=N;
id=new int[N];
sz=new int[N];
for(int i=0;i<N;i++){
id[i]=i;
sz[i]=1;
}
}
private int find(int p){
while(p!=id[p]){//找出根结点
p=id[p];
}
return p;
}
private void union(int p,int q){
int i=find(p);
int j=find(q);
if(i==j)return;
if(sz[i]<sz[j]){
id[i]=j;sz[j]+=sz[i];
}else{
id[j]=i;sz[i]+=sz[j];
}
count--;
}
//对联通分量进行计数
public int count(){return count;}
//判断是否连接
public boolean connected(int p,int q){
return find(p)==find(q);
}
}
