基础算法-Union-Find(动态连通性)--quick-fi

今天学习的算法是比较基础和典型的算法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