首页 > 代码库 > 并查集(Union-Find)

并查集(Union-Find)

 

目的:主要用来解决动态连通性问题 (数据结构用来表征站点之间的连通性,算法主要利用数据结构,解决问题,比如,判断站点之间是否连通。由此,数据结构的特性对算法性能有着最直接的影响,数据结构和算法设计就是两个好基友,谁也不能脱离谁。)

应用:声明的两个变量是否指向同一个对象(内存空间);网络中两个主机之间是否相连;两个数据是否在同一个集合里。
输入:整数对序列, 例如<p, q>对,代表p和q是相连通的。
方法:对输入的<p,q>对进行判断,若已有的值对表明p,q已经连通,则忽视这一输入,否则将他们所在的component进行归并。

基于上述要求,提出下述几个最基本的API:

UF(int N)  用(0, N-1)初始化N个站点。

void union(int p, int q)  如果p与q这两个站点处于不同的compnent中,将这两个站点所在的component归并。

int find(int p) 返回站点p所在的component标号。

boolean connected(int p, int q) 判断站点p与q是否处于同一个component中。

int count() 返回component数目。

 

基本java的代码实现:

public class UF

{

private int[] id;

private int count; //UF数据结构需要维护两个量,一个是id数组,存储所有的站点对应的component号;还有一个是count,总计有多少个components。

public UF(int N) {count N; id =new int[N]; for(int i=0; i<N; i++) id[i]=i;} //构造函数,初始化成员变量。

public void union(int p, int q);

public int find(int p){return id[p];}

boolean connected(int p, int q} { if(find(p)==find(q) return true; else return false;}

public int count() { return count;}

}

public void union(int p, int q)

{

   int pID=find(p);

   int qID=find(q);

  if(pID==qID) return; //如果它俩有处在同一个component中,则啥也不做。

  for(int i=0; i<id.length;i++)

      if(id[i]==pID) id[i]=qID;  //如果p和q是不相连的,将这两个站点所在的component合并,p所在的component中所有站点的id号都被替换为q所在component站点号。其实这是随意的,也可以用q的站点号来替换掉p所在component的所有站点号。

  count--; //component数目消失一个。

}

 

并查集(Union-Find)