The problem that we consider is not a toy problem; it is a fundamental computational task, and the solution that we develop is of use in a variety of applications, from percolation in physical chemistry to connectivity in communications networks. We start with a simple solution, then seek to understand that solution’s performance characteristics, which help us to see how to improve the algorithm.
Dynamic connectivity We start with the following problem specification: The input is a sequence of pairs of integers, where each integer represents an object of some type and we are to interpret the pair p q as meaning "p is connected to q." We assume that "is connected to" is an equivalence relation, which means that it is:
■ Reflexive : p is connected to p.
■ Symmetric : If p is connected to q, then q is connected to p.
■ Transitive : If p is connected to q and q is connected to r, then p is connected to r.
An equivalence relation partitions the objects into equivalence classes. In this case, two objects are in the same equivalence class if and only if they are connected. Our goal is to write a program to filter out extraneous pairs (pairs where both objects are in the same equivalence class) from the sequence. In other words, when the program reads a pair p q from the input, it should write the pair to the output only if the pairs it has seen to that point do not imply that p is connected to q. If the previous pairs do imply that p is connected to q, then the program should ignore the pair p q and proceed to read in the next pair. The figure on the facing page gives an example of this process. To achieve the desired goal, we need to devise a data structure that can remember sufficient information about the pairs it has seen to be able to decide whether or not a new pair of objects is connected. Informally, we refer to the task of designing such a method as the dynamic connectivity problem. This problem arises applications such as the following:
Networks. The integers might represent computers in a large network, and the pairs might represent connections in the network. Then, our program determines whether we need to establish a new direct connection for p and q to be able to communicate or whether we can use existing connections to set up a communications path. Or, the integers might represent contact sites in an electrical circuit, and the pairs might represent wires connecting the sites. Or, the integers might represent people in a social network, and the pairs might represent friendships. In such applications, we might need to process millions of objects and billions of connections.
Variable-name equivalence. In certain programming environ- ments, it is possible to declare two variable names as being equivalent (references to the same object). After a sequence of such declarations, the system needs to be able to determine whether two given names are equivalent. This application is an early one (for the FORTRAN programming language) that motivated the development of the algorithms that we are about to consider.
Mathematical sets. On a more abstract level, you can think of the integers as belonging to mathematical sets. When we process a pair p q, we are asking whether they belong to the same set.If not, we unite p’s set and q’s set, putting them in the same set.
To specify the problem, we develop an API that encapsulates the basic operations that we need: initialize, add a connection between two sites, identify the component containing a site, determine whether two sites are in the same component, and count the number of components. Thus, we articulate the following API:
public class UF { public UF(int N) {} // initialize N sites with integer names (0 to N-1) void union(int p, int q) {} // add connection between p and q int find(int p) {} // component identifier for p (0 to N-1) // return true if p and q are in the same component boolean connected(int p, int q) {} int count() {} // number of components }
The union() operation merges two components if the two sites are in different com- ponents, the find() operation returns an integer component identifier for a given site, the connected() operation determines whether two sites are in the same component, and the count() method returns the number of components. We start with N components, and each union() that merges two different components decrements the number of components by 1.
public class UF { private int[] id; // id[i] = parent of i private int[] sz; // sz[i] = number of objects in subtree rooted at i private int count; // number of components /** * Create an empty union find data structure with N isolated sets. * * @throws java.lang.IllegalArgumentException * if N < 0 */ public UF(int N) { if (N < 0) throw new IllegalArgumentException(); count = N; id = new int[N]; sz = new int[N]; for (int i = 0; i < N; i++) { id[i] = i; sz[i] = 1; } } /** * Return the id of component corresponding to object p. * * @throws java.lang.IndexOutOfBoundsException * unless 0 <= p < N */ public int find(int p) { if (p < 0 || p >= id.length) throw new IndexOutOfBoundsException(); while (p != id[p]) { p = id[p]; } return p; } /** * Return the number of disjoint sets. */ public int count() { return count; } /** * Are objects p and q in the same set? * * @throws java.lang.IndexOutOfBoundsException * unless both 0 <= p < N and 0 <= q < N */ public boolean connected(int p, int q) { return find(p) == find(q); } /** * Replace sets containing p and q with their union. * * @throws java.lang.IndexOutOfBoundsException * unless both 0 <= p < N and 0 <= q < N */ public void union(int p, int q) { int i = find(p); int j = find(q); if (i == j) return; // make smaller root point to larger one if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; } else { id[j] = i; sz[i] += sz[j]; } count--; } }
Analysis of complexity:
相关推荐
数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 ...
不相交集ADT8.1 等价关系8.2 动态等价性问题8.3 基本数据结构8.4 灵巧求并算法8.5 路径压缩8.6 按秩求并和路径压缩的最坏情形8.6.1 Union/Find算法分析8.7 一个应用总结练习参考文献第9章 图论算法9.1 若干定义9.1.1...
C#,图论与图算法,无向图(Graph)回环(Cycle)的不相交集(disjoint)或并集查找(union find)判别算法与源代码 不相交集数据结构是一种数据结构,它跟踪划分为多个不相交(非重叠)子集的一组元素。联合查找...
∷相关函数:Find函数 Union函数 1.4.17 树的二叉链表存储的基本操作 193 范例1-71 树的二叉链表存储的基本操作 193 ∷相关函数:LevelOrderTraverse函数 1.4.18 二叉树的三叉链表存储的基本操作 201 范例1-72 ...
数据结构与算法分析C++语言描述 中文第四版 高清含书签 2016本版特色如下: *书中的阐述和算法均用C++新标准C++11的代码实现。 *unordered_map两个类模板的简要讨论。 *增加了基数排序和与选择相关问题下界的证明。...
学习的大部分基础数据结构和相关的算法 实现语言主要是C/C++ BST: 二分搜索树 BubbleSort: 冒泡排序 CircleLinkList: 循环链表 Expression: 表达式求值 Fibonacci: 斐波那契数列 Floyd: 弗洛伊德算法 Graphic: 图...
基于Union-Find数据结构实现Kruskal求最小生成树,代码设计及变量命名附详细注释。基于Union-Find数据结构实现Kruskal求最小生成树,代码设计及变量命名附详细注释。
创建一个新的 union-find 数据结构,包含其作为单例集的参数: user=> (use 'jordanlewis.data.union-find) user=> (def uf (union-find 1 2 3 4 5)) user=> uf {5 [5], 4 [4], 3 [3], 2 [2], 1 [1]} 添加一个...
数据结构算法实现(严蔚敏版配套实现程序) 1.1 数组和字符串 2 1.1.1 一维数组的倒置 2 范例1-1 一维数组的倒置 2 ∷相关函数:fun函数 1.1.2 一维数组应用 3 范例1-2 一维数组应用 3 1.1.3 一维数组的高级应用 5 ...
联合查找是一种数据结构,可保持不相交的集合(称为连接的组件或简称为组件)成员身份,并使合并(联合)两个组件以及查找两个元素是否已连接(即属于同一组件)更加容易。 )。 这实现了“加权快速工会与路径压缩...
用Java实现数据结构和算法 动态数组实现 帕斯卡三角形的实现(锯齿状数组) 打印所有素数直到给定 n。 定理:假设所有数字都是素数,直到被证明为假。 单链表 标准单向链表:push/pop front、insert(i)、remove(i)、...
这是UNION-FIND数据结构的小型独立C ++ 11实现,具有按等级压缩和按路径合并以及一些附加功能。它支持并发find() , same()和unite()调用,如本文所述 联合发现问题的免等待并行算法,作者:Richard J. Anderson和...
2、内容全面:全面论述排序、搜索、图处理和字符串处理的算法和数据结构,涵盖每位程序员应知应会的50种算法 3、全新修订的代码:全新的Java实现代码,采用模块化的编程风格,所有代码均可供读者使用 4、与...
西安电子科技大学《算法设计与分析》上机题。渗透问题(Percolation) 使用合并-查找(union-find)数据结构,编写程序通过蒙特卡罗模拟(Monte Carlo simulation)来估计渗透阈值的值。
∷相关函数:Find函数 Union函数 1.4.17 树的二叉链表存储的基本操作 193 范例1-71 树的二叉链表存储的基本操作 193 ∷相关函数:LevelOrderTraverse函数 1.4.18 二叉树的三叉链表存储的基本操作 201 范例1-72 ...
Chapter 8 uses the new union/find analysis by Seidel and Sharir, and shows the O( Mα(M,N) ) bound instead of the weaker O( Mlog∗ N ) bound in prior editions. Chapter 12 adds material on suffix ...
1.5 案例研究:union-find算法 136 1.5.1 动态连通性 136 1.5.2 实现 140 1.5.3 展望 148 第2章 排序 152 2.1 初级排序算法 153 2.1.1 游戏规则 153 2.1.2 选择排序 155 2.1.3 ...
1.5 案例研究:union-find算法 136 1.5.1 动态连通性 136 1.5.2 实现 140 1.5.3 展望 148 第2章 排序 152 2.1 初级排序算法 153 2.1.1 游戏规则 153 2.1.2 选择排序 155 2.1.3 插入排序 ...