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

今天是基于昨天实现的算法Union-Find（动态连通性）的优化。

题目介绍

问题的输入是一系列整数对，其中每个整数都表示一种数据类型的对象，一对整数对p,q可以理解成：“p和q是相连的”。

最典型的使用场景就是在一个大型的计算机网络集群中，一个整数对表示两台机器是可以通信的。这样给定任意两个整数，我们可以判断两个整数是否可以通过一系列的线链接起来，也即是是否可以相连。

我们先看下图吧：

动态连通性--题目.png

抽象一下的话，我们可以将所有整数看成多个集合，每个集合内的整数都是相连的。每个整数又称为触点。

算法需要提供如下API接口：

初始化
连接两个触点
获得包含某个触点的分量
判断两个触点是否在同一分量中
获得分量的数量

实现思路(优化)

先看下实现思路图：

动态连通性--优化.png

今天的实现使用的是森林的表示法。如上图所示，我们使用的仍然是一个整数数组，每个数组初始化时其值等于下标。

首先我们将数组中的值等于下标理解成一个指向自己的节点。当我们将两个触点相连时，是指我们将其中的一个触点指向另一个触点。也就是将其中一个输入整数的下标对应的值存储为另一个整数的下标。

最终经过上述的过程后，我们留下的就是类似的三棵树。当然，上述使用的数据不够均衡，导致结果为三个链表。

我们简单分析下两种算法的时间复杂度：

1.使用简单实现的union方法时间复杂度为：O(3N)，因为每次都要根据输入的整数遍历数组。再加上外层main方法的遍历。

2.使用森林表示法的union方法时间复杂度为：O(2N)。

实现代码

public class QuickUnionUF implements QuickUF {

 private int[] a;
 private int count;

 public QuickUnionUF(int[] a) {
 this.a = a;
 count = a.length;
 }


 @Override
 public int count() {
 return count;
 }

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

 @Override
 public int find(int p) {
 while (p != a[p]) p = a[p];
 return p;
 }

 @Override
 public void union(int p, int q) {
 int i = find(p);
 int j = find(q);
 if (a[i] == a[j]) return;
 a[i] = a[j];
 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;
 }

 QuickUnionUF quickUnionUF = new QuickUnionUF(a);
 quickUnionUF.union(1, 5);
 quickUnionUF.union(2, 6);
 quickUnionUF.union(6, 7);
 quickUnionUF.union(4, 8);
 quickUnionUF.union(7, 8);


 StdOut.println(quickUnionUF.count());
 StdOut.println(quickUnionUF.find(0));
 StdOut.println(quickUnionUF.find(4));
 StdOut.println(quickUnionUF.find(6));
 StdOut.println(quickUnionUF.find(3));
 StdOut.println(quickUnionUF.connected(2, 4));
 StdOut.println(quickUnionUF.connected(1, 2));
 }
}

算法相关实现源码地址：https://github.com/xiekq/rubs-algorithms

最后编辑于：2020.06.13 22:17:09