Union Find

Leave a comment

March 19, 2017 by oneOokay

这里讲的超级详细: https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

Union Find主要是用于: “Network connectivity”

给你N个点和一些边的集合edges[][]: 用Union Find可以判断

  1. 图是否存在环
  2. 某两点之间是否是联通的(两点间是否存在一条通路): Find
  3. 一空有多少个联通的区域(区域之间互相不连通): 如果只有一个的话,那么该图就是一个连通图
  4. 给两个点,如果存在通路的话把他们联通起来….Union
  5. 还能够建树.

基本的数据结构是:

  • 一个数组:int[] ids: size为n(点的个数).i代表lable为i的点.ids[i]代表这个label == i的点所处于的联通的区域(用int表示):
    • 所以如果ids[m] == ids[n]:说明点m和点n是联通的.
    • 初始化ids[i] = i;
      • i    : 0,1,2,3,4,5
      • ids: 0,1,1,2,4,2
      • 代表了:点1和2是联通的;3和5是联通的;1,4 各自为一个孤立的点.
  • 可以用一个int count: 来代表当前的联通的区域个数.
    • 初始化为n:每做一次成功的union,count –.
  • 读入edges[i][0] = v1和edges[i][1] = v2:
  • find(v1, v2) 如果ids[v1] == ids[v2]说明v1和v2是联通的;否则两者不连通
  • union(v1, v2) : 把所有ids[i] == ids[v1]的值更新成ids[i] = ids[v2]

一个挺基本挺有用的形式大概是这样的: (Graph Valid Tree的UnionFind的解法)这里省略了Find,把Find放到了Union里面.

public boolean validTree(int n, int[][] edges) {
 UnionFind uf = new UnionFind(n);
 for (int i = 0;i < edges.length; i ++){
 if (!uf.union(edges[i][0], edges[i][1])) return false;
 }
 return uf.count == 1;
 }
public class UnionFind {
        int[] ids;
        int count;
        public UnionFind(int n){
            ids = new int[n];
            for (int i = 0; i < n; i ++){
                ids[i] = i;
            }
            count = n;
        }
        
        public boolean union(int m, int n){
            if (ids[m] == ids[n]) return false;//存在环
            int vm = ids[m];
            for (int i = 0; i < ids.length; i ++){
                if (ids[i] == vm)
                    ids[i] = ids[n];
            }
            count --;
            return true;
        }
    }

如何find和如何union是影响整个算法速度的关键,以及所形成的树的形状.

所以UnionFind的写法主要有:

Quick-find:

  • id[i]的值:如果id[i]的值相同,那么i是联通的.
  • Find的时候1次操作: id[i] = v
  • Unite的时候N次操作:把所有ids[i] == ids[m]的i赋值成ids[n](上面的Graph Valid Tree就是这个写法). 这里可能有很多元素需要重新赋值.
  • 太慢了(Union太慢了).时间复杂度能够达到O(MN):其中N为顶点的个数,M为进行unite的次数.
  • 形成一个很”平”的树:但是too expensive to keep them flat…

Quick-Union:

  • ids[i]:存的是i的上一级的root的index
  • 引入了一个root method: root(int i)返回i的最终的一个parent. O(depth of i) 直到ids[i]==i为止.
  • find(m, n):判定root(m)和root(n)是否相等. (太慢了)
    •  O (depth of m 和 n), worst case: O(N)
  • Unite(m,n):分别找到m的root和n的root,再使得m的root变成n的root(在两个root之间连一条线,使得两个root一个变成新root,一个变成一个儿子). (做union的时候其实又做了一遍find或者说需要先做find才能做union)
  • 因为包含了find: O(depth of m 和 n) worst case: O(N)
  • 形成一个比较”高”的树:因为每次unite的时候都是把一个树接在另一个树下变成一个子树.

Weighted quick-union:

  • 记录每一个联通区域的size(含有多少个点):
  • sz[] = new int[n]. sz[i]代表以i为root的一个树中一共有多少个点.
  • 把size小的树(区域)连到size大的树(区域),从而尽量的不要产生一个很”高”的树
  • 这样产生的树的深度最多为lgN. 所以Union 和 Find的时间复杂度是: O(lgN)
  • 代码实现:和quick-union基本差不多;Find是一模一样的
  • Union:
if (sz[i] < sz[i]) { ids[i] = j; sz[j] += sz[i]; }
else {ids[j] = i; sz[i] += sz[k]; }

最优来了: Weighted quick-union with path compression: O(N + M lg N)

root()中:在while loop里面找root的同时,把每个访问的i 都指向他的root的root(grandparent);使得树超级扁平….

while (i != ids[i]) { id[i] = id[id[i]]; i = id[i]; } return i;

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: