devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Union-Find 算法（并查集）_实现 union-find data structure matlab

作者：IT小白 | 2024-03-15 18:20:41

赞

踩

实现 union-find data structure matlab
作者：disappearedgod
时间：2014-5-7

前言

参考《算法》第四版的内容，并融入了Algorithm，Part I（Princeton）的讲义

0. 介绍

这里讨论的是一个网络连接的问题。看图画中的两个点是否能够连接上。

1. 动态连通性

问题的输入是一列整数对，其中每个整数都表示一个某种类型的对象，一对整数p q可以被理解为"p和q是相连的 "。我们假设“相连”是一种对等的关系，也就意味着：
  • 自反性：p和p是相连的
  • 对称性：如果p和q是相连的，那么q和p也是相连的
  • 传递性：如果p和q是相连的且q和r是相连的，那么p和r也是相连的。
上述对等关系能够将对象分为多个等价类（当且仅当两个对象相连时它们才属于同一个等价类）。

也就是，当程序从输入中读取了整数对（p q）时，如果一直的所有整数对都不能说明p和q是相连的，那么则将这一对整数写到输出中。如果已知的数据可以说明p和q是相连的，那么程序应该忽略（p q）这对整数并继续处理输入中的下一对整数。
我们设计了一份API来封装所需的基本操作:初始化、连接两个触点、判断包含某个触点的分量、判断两个触点是否存在于同一个分量之中以及返回所有分量的数量。
public class UF
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)
boolean connected(int p, int q)                return true if p and q are in the same component
int count()                                              number of components

所有的实现都应该：
定义一种数据结构表示一直的连接
基于此数据结构实现高效的union()、find()、connected()和count()方法

我们的目的是找到一条路径：

首先，先看一下UF的测试用例

  1. public static void main(String[] args) {
  2.         int N = StdIn.readInt();//对象的个数
  3.         UF uf = new UF(N);
  4.         while (!StdIn.isEmpty()) {//输入整数对
  5.             int p = StdIn.readInt();
  6.             int q = StdIn.readInt();
  7.             if (uf.connected(p, q)) continue;
  8.             uf.union(p, q);
  9.             StdOut.println(p + " " + q);
  10.         }
  11.         StdOut.println(uf.count() + " components");
  12.     }



测试用例的一个输入是：

  1. 10
  2. 4 3
  3. 3 8
  4. 6 5
  5. 9 4
  6. 2 1
  7. 8 9
  8. 5 0
  9. 7 2
  10. 6 1
  11. 1 0
  12. 6 7


2. 实现

对于上述这样的动态连接问题，我们用下面几种方法进行数显。

2.1 quick-find 算法

2.1.1 算法介绍

我们想构造这样一种数据类型


其实，我们用了一个一下这个方法（例如添加一条边1-6）


我们举几个例子吧：

先从0-链接开始


链接操作union(4,3) 就是把id为4的数值改为id为3的数值

、




connected（）判断是否有链接




如下图来做这个操作


2.1.2 算法实现

根据上述介绍，我们可以写这样段代码

  1. public class QuickFindUF {
  2.     private int[] id;    // id[i] = component identifier of i
  3.     private int count;   // number of components
  4.  
  5.     /**
  6.      * Initializes an empty union-find data structure with N isolated components 0 through N-1.
  7.      * @throws java.lang.IllegalArgumentException if N < 0
  8.      * @param N the number of objects
  9.      */
  10.     public QuickFindUF(int N) {
  11.         count = N;
  12.         id = new int[N];
  13.         for (int i = 0; i < N; i++)
  14.             id[i] = i;
  15.     }  
  16.  
  17.     /**
  18.      * Are the two sites <tt>p</tt> and <tt>q/tt> in the same component?
  19.      * @param p the integer representing one site
  20.      * @param q the integer representing the other site
  21.      * @return <tt>true</tt> if the two sites <tt>p</tt> and <tt>q</tt> are in
  22.      *    the same component, and <tt>false</tt> otherwise
  23.      * @throws java.lang.IndexOutOfBoundsException unless both 0 <= p < N and 0 <= q < N
  24.      */
  25.     public boolean connected(int p, int q) {
  26.         return id[p] == id[q];
  27.     }
  28.   
  29.     /**
  30.      * Merges the component containing site<tt>p</tt> with the component
  31.      * containing site <tt>q</tt>.
  32.      * @param p the integer representing one site
  33.      * @param q the integer representing the other site
  34.      * @throws java.lang.IndexOutOfBoundsException unless both 0 <= p < N and 0 <= q < N
  35.      */
  36.     public void union(int p, int q) {
  37.         if (connected(p, q)) return;
  38.         int pid = id[p];
  39.         for (int i = 0; i < id.length; i++)
  40.             if (id[i] == pid) id[i] = id[q]; 
  41.         count--;
  42.     }
  43. 	
  44. 	/**
  45.      * Returns the number of components.
  46.      * @return the number of components (between 1 and N)
  47.      */
  48.     public int count() {
  49.         return count;
  50.     }
  51. 	/**
  52.      * Returns the component identifier for the component containing site <tt>p</tt>.
  53.      * @param p the integer representing one site
  54.      * @return the component identifier for the component containing site <tt>p</tt>
  55.      * @throws java.lang.IndexOutOfBoundsException unless 0 <= p < N
  56.      */
  57.     public int find(int p) {
  58.         return id[p];
  59.     }
  60. }

2.1.3 算法分析

在quick-find 算法中，每次find()调用只需要访问数组一次，而归并两个分量的union()操作访问数组的次数在(N+3)到(2N+1)之间。（uion中调用两次find()，jiancha id[]数组中全部N个元素并改变他们中的1到N-1个元素）。

如果最终结果是只得到一个连通分量(所有数组值都相同)，只扫调用（N-1）次union,即至少需要N+3TimesN-1次——N^2次操作。


2.2 quick-union 算法

2.2.1 介绍

这个算法主要是提高了union()方法的速度，它和quick-find方法互补。

他也是基于相同的数据结构（id数组），单赋予了不同的意义。这里采用了树（根）的概念。

我们由p和q的链接分别找到它们的根触点，然后只需要将一个根触点链接到另一个即可，讲一个分量重命名为另一个分量，因此叫做quick-union。

我现在看一下是如何做Union() 和Connect()的


Union(a,b)是将b的根节点作为a的根节点的根节点








connect(a,b)是看他们的根节点是否相同




下面看一下这个例子中的树是如何建立的


2.2.2实现


  1. public class QuickUnionUF {
  2.     private int[] id;    // id[i] = parent of i
  3.     private int count;   // number of components
  4.  
  5.     /**
  6.      * Initializes an empty union-find data structure with N isolated components 0 through N-1.
  7.      * @throws java.lang.IllegalArgumentException if N < 0
  8.      * @param N the number of objects
  9.      */
  10.     public QuickUnionUF(int N) {
  11.         id = new int[N];
  12.         count = N;
  13.         for (int i = 0; i < N; i++) {
  14.             id[i] = i;
  15.         }
  16.     }
  17.  
  18.     
  19.  
  20.     /**
  21.      * Returns the component identifier for the component containing site <tt>p</tt>.
  22.      * @param p the integer representing one site
  23.      * @return the component identifier for the component containing site <tt>p</tt>
  24.      * @throws java.lang.IndexOutOfBoundsException unless 0 <= p < N
  25.      */
  26.     public int find(int p) {
  27.         while (p != id[p])
  28.             p = id[p];
  29.         return p;
  30.     }
  31.  
  32.     /**
  33.      * Are the two sites <tt>p</tt> and <tt>q</tt> in the same component?
  34.      * @param p the integer representing one site
  35.      * @param q the integer representing the other site
  36.      * @return <tt>true</tt> if the sites <tt>p</tt> and <tt>q</tt> are in the same
  37.      *    component, and <tt>false</tt> otherwise
  38.      * @throws java.lang.IndexOutOfBoundsException unless both 0 <= p < N and 0 <= q < N
  39.      */
  40.     public boolean connected(int p, int q) {
  41.         return find(p) == find(q);
  42.     }
  43.  
  44.   
  45.     /**
  46.      * Merges the component containing site<tt>p</tt> with the component
  47.      * containing site <tt>q</tt>.
  48.      * @param p the integer representing one site
  49.      * @param q the integer representing the other site
  50.      * @throws java.lang.IndexOutOfBoundsException unless both 0 <= p < N and 0 <= q < N
  51.      */
  52.     public void union(int p, int q) {
  53.         int rootP = find(p);
  54.         int rootQ = find(q);
  55.         if (rootP == rootQ) return;
  56.         id[rootP] = rootQ; 
  57.         count--;
  58.     }
  59.  
  60.     /**
  61.      * Returns the number of components.
  62.      * @return the number of components (between 1 and N)
  63.      */
  64.     public int count() {
  65.         return count;
  66.     }
  67.     
  68.  
  69.  
  70. }

2.2.3 评价

这个方法的最好的时间复杂度是线性的，最坏时间复杂度也还是平方的。


好处是：quick-union 算法看做是quick-find算法的一种改良，因为它解决了quick-find算法中最主要的问题（Union（）操作总是线性级别的）。

我们发现最坏时间复杂度高是因为树的深度太深。

2.3 加权quick-union算法

2.3.1 介绍

简单的修改quick-union算法就能保证最坏情况不能发生。我们将记录每一棵树的大小并总是将较小的树链接到较大的树上。这项改动需要添加一个数组和一些代码在记录树中的节点数。


2.3.2 实现

  1. public class WeightedQuickUnionUF {
  2.     private int[] id;    // id[i] = parent of i
  3.     private int[] sz;    // sz[i] = number of objects in subtree rooted at i
  4.     private int count;   // number of components
  5.  
  6.     /**
  7.      * Initializes an empty union-find data structure with N isolated components 0 through N-1.
  8.      * @throws java.lang.IllegalArgumentException if N < 0
  9.      * @param N the number of objects
  10.      */
  11.     public WeightedQuickUnionUF(int N) {
  12.         count = N;
  13.         id = new int[N];
  14.         sz = new int[N];
  15.         for (int i = 0; i < N; i++) {
  16.             id[i] = i;
  17.             sz[i] = 1;
  18.         }
  19.     }
  20.  
  21.     /**
  22.      * Returns the number of components.
  23.      * @return the number of components (between 1 and N)
  24.      */
  25.     public int count() {
  26.         return count;
  27.     }
  28.  
  29.     /**
  30.      * Returns the component identifier for the component containing site <tt>p</tt>.
  31.      * @param p the integer representing one site
  32.      * @return the component identifier for the component containing site <tt>p</tt>
  33.      * @throws java.lang.IndexOutOfBoundsException unless 0 <= p < N
  34.      */
  35.     public int find(int p) {
  36.         while (p != id[p])
  37.             p = id[p];
  38.         return p;
  39.     }
  40.  
  41.     /**
  42.      * Are the two sites <tt>p</tt> and <tt>q</tt> in the same component?
  43.      * @param p the integer representing one site
  44.      * @param q the integer representing the other site
  45.      * @return <tt>true</tt> if the two sites <tt>p</tt> and <tt>q</tt>
  46.      *    are in the same component, and <tt>false</tt> otherwise
  47.      * @throws java.lang.IndexOutOfBoundsException unless both 0 <= p < N and 0 <= q < N
  48.      */
  49.     public boolean connected(int p, int q) {
  50.         return find(p) == find(q);
  51.     }
  52.  
  53.   
  54.     /**
  55.      * Merges the component containing site<tt>p</tt> with the component
  56.      * containing site <tt>q</tt>.
  57.      * @param p the integer representing one site
  58.      * @param q the integer representing the other site
  59.      * @throws java.lang.IndexOutOfBoundsException unless both 0 <= p < N and 0 <= q < N
  60.      */
  61.     public void union(int p, int q) {
  62.         int rootP = find(p);
  63.         int rootQ = find(q);
  64.         if (rootP == rootQ) return;
  65.  
  66.         // make smaller root point to larger one
  67.         if   (sz[rootP] < sz[rootQ]) { id[rootP] = rootQ; sz[rootQ] += sz[rootP]; }
  68.         else                         { id[rootQ] = rootP; sz[rootP] += sz[rootQ]; }
  69.         count--;
  70.     }
  71.  
  72.  
  73.  
  74. }

2.3.3 评价

下图为例子输入构造和上述最坏情况


对于100个点做88次union方法来说


2.4 总结

各种UF的性能比较


所有操作的总成本（横轴为链接总数，纵轴为访问数组的次数）


声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/243568
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号