1.3:Union-Find算法-----quick-find算法

时间:2022-09-05 16:34:07

接下来实现Union-Find算法的第一种实现方式:quick-find算法

首先是数据结构

我们用一个长度为N的整型数组id[] 来表示图中各个点。一开始初始化id[x] = x,id[x]中x代表点的标号,如果其中两点p, q相连通,则id[p] = id[q]。

find()方法:

只需检查id[p]和id[q]是否相等。

union(p, q)方法:

遍历整个数组,将数组里所有id与id[p]相等的都改成id[p]。


下面是代码实现

class QuickFindUF {
private int[] id;
private int count;

public QuickFindUF(int n) {
id = new int[n];
for(int i = 0; i < n; i++)
id[i] = i;
count = n;
}

public int count() {
return count;
}

public boolean connected(int p, int q) {
return find(p) == find(q);
}

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

public void union(int p, int q) {
int pid = id[p];
int qid = id[q];

for(int i = 0; i < id.length; i++)
if(id[i] == pid)id[i] = qid;
}
}
对算法的分析:

初始化操作:花费时间级数为N

find():花费时间级数为1

union():在最坏的情况下时间为N