今天学习的算法是比较基础和典型的算法Union-Find（动态连通性）。
题目介绍
问题的输入是一系列整数对，其中每个整数都表示一种数据类型的对象，一对整数对p,q可以理解成：“p和q是相连的”。
最典型的使用场景就是在一个大型的计算机网络集群中，一个整数对表示两台机器是可以通信的。这样给定任意两个整数，我们可以判断两个整数是否可以通过一系列的线链接起来，也即是是否可以相连。
我们先看下图吧：
动态连通性--题目.png
抽象一下的话，我们可以将所有整数看成多个集合，每个集合内的整数都是相连的。每个整数又称为触点。
算法需要提供如下API接口：
-
初始化
-
连接两个触点
-
获得包含某个触点的分量
-
判断两个触点是否在同一分量中
-
获得分量的数量
实现思路
先看下实现思路图：
动态连通性--解题.png
我们先看下最简单的实现方法：
1.我们维护一个整数数组，其中下标表示整数值，数组的值表示其连通分量的触点所在下标。
2.每次输入两个整数时，我们只需要获得其中一个触点的值记为N，然后遍历数组，将所有值等于N的触点（也就是同一个分量下的所有触点）的值改为另外一个整数的值。这样输入两个整数的所有触点的值就一样了。
3.总的来说就是每个分量都有一个共同的值，每次输入两个整数，只要他们不是在同一个分量中，就将其中一个整数所在的分量的所有触点的值都改为另一个。
实现代码
public class QuickFindUF implements QuickUF {
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 = id.length;
}
@Override
public int count() {
return count;
}
@Override
public boolean connected(int p, int q) {
return id[p] == id[q];
}
@Override
public int find(int p) {
return id[p];
}
@Override
public void union(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;
}
}
count--;
}
public static void main(String[] args) {
int N = 9;
int[] a = new int[9];
for (int i = 0; i < 9; i++) {
a[i] = i;
}
QuickFindUF quickFindUF = new QuickFindUF(9);
quickFindUF.union(1, 5);
quickFindUF.union(2, 6);
quickFindUF.union(6, 7);
quickFindUF.union(4, 8);
quickFindUF.union(7, 8);
StdOut.println(quickFindUF.count());
StdOut.println(quickFindUF.find(0));
StdOut.println(quickFindUF.find(4));
StdOut.println(quickFindUF.find(6));
StdOut.println(quickFindUF.find(3));
StdOut.println(quickFindUF.connected(2, 4));
StdOut.println(quickFindUF.connected(1, 2));
}
}
算法相关实现源码地址：https://github.com/xiekq/rubs-algorithms
网友评论