Union Find Sets 并查集以及最小生成树

Leave a comment

March 19, 2017 by oneOokay

  • 什么是Union Find Sets
  • UFS的操作
  • 最小生成树算法:Kruskal算法的应用

Union Find Sets: 是模拟数学中的”集合”. 只有两种操作:

  • Union(a,b):把a元素和b元素所在的集合合并
  • Find(x): 返回x元素所在的集合

数据表示:

如何表示一个集合? 任取集合中的一个元素作为代表元素.

  • [1,2,7,4] : find(1) = 7; find(2) = 7; find(7) = 7; find(4) = 7.

两个集合合并之后如何表示?两个代表元素任选一个作为新的代表元素.一般都选元素多的那个集合的代表元素作为新的代表元素.

  • [8, 9]: find(8) = 8; find(9) = 8. 与集合”7″合并之后:
  • find(8) = 7; find(9) = 7

具体实现:

用树形结构实现,根节点放集合代表元素,其他元素指向根.

  • 用一个int[] f数组来表示这棵数.
  • 非根节点的值:f[i] = 父节点的编号.
  • 根节点的值:f[root] = 集合元素的个数 * (-1) : 负数表示以区分.
    • 注意这里根据题目情况的不同,也可以用f[root] == root来表示root.对应的初始化是f[i] = i.
  • [1,2,7,4] : f[1] = 7; f[2] = 7; f[4] = 7; find[7] = -4.

Union集合合并操作: 见图. 注意union的话,更新值的时候一定要: 找到两个值的根,对这个两个根进行更新

  1. 更新新树根的元素的个数 f[7] = f[7] + f[8]
  2. 另一个根指向新的树根 f[8] = 7.

Find操作与路径压缩: 见图.

  • Find的时候把沿路所有的点都指向根,减少后续Find操作的时间.

代码实现:

//初始化代码
public UFS(int n){
    f = new int[n];
//初始化的时候每一个点都是独立的,集合里面仅有一个元素,所以初始值为-1
//注意根据题目情况的不同,f[i]也可初始化为i.
    for(int i = 0; i < n; i ++){
        f[i] = -1;
    }
//同时也可以初始化一下size = n;最后可以知道最终的联通区域有多少个.
}
//Find代码
public int find(int x){
    //当前节点为根节点,根节点的index就是当前区域的编号/代表元素
    //同时也可以知道,当前联通区域内一共有多少个点: -x
    //如果初始化为f[root] == root的话这里就是: if(f[x] == x).
    if(f[x] < 0){ 
        return x;
    }
    //find的同时进行路径压缩
    f[x] = find(f[x]);
    return f[x];
}
//Union
public void union(int a, int b){
    a = find(a);//a的联通区域的根的编号/index
    b = find(b);//b的联通区域的根的编号/index
    //a和b已经是联通区域了,不需要再做任何事情.
    if(a == b) return;
//此时a,b已经为他们的根的index了, 所以f[a],f[b]都为负数.
//a区域的点数>b区域的点数,把a区域作为新的根
    if(f[a] < f[b]){ 
        f[a] += f[b];//更新新的根的区域的数目
        f[b] = a;//把旧的根指向新的根
    } else {
        f[b] += f[a];
        f[a] = b;
    }
    注意这里可以根据题目,来进行size --从而得到最终的联通区域的个数
}

图:点和边的集合. 若 节点数 n – 1 < 边数 m: 说明一定有环.

数:无环联通图. 节点数 n – 1 = 边数 m

什么是最小生成树: 一个图选其中的一些边构成树,边的权值(长度)加起来最小

算法:Kruskal 和 Prim (略过)

Kruskal:

  1. 边从小到大排序
  2. 排序之后扫描所有的边,在不形成环的情况下依次加入到图中(加入改边后不形成环就加入, 如果形成环就舍弃改边)

如何判定加入后是否形成环? Union Find Sets.

时间复杂度:(m为边数)

  1. 排序: 快排O(mlogm)
  2. 不成环加入:扫描之后并查集O(m)
  3. 总体: O(mlogm).

最小生成树


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

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

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

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

基本的数据结构是:

  • 一个数组:int[] ids: size为n(点的个数).i代表lable为i的点.ids[i]代表这个label为i的点所处于的联通区域(的值)(用int表示):
    • 所以如果ids[m] == ids[n]:说明点m和点n是联通的.
    • 初始化ids[i] = i:表示每个点只与自身联通.
      • 例子如果给以下的ids array:
      • i    : 0,1,2,3,4,5
      • ids: 0,1,1,2,4,2
      • 代表了:点1和2是联通的(因为联通区域同为1);3和5是联通的(联通区域同为2);0,4 各自为一个孤立的点,没有其他的点与他联通.
  • 可以用一个int count: 来代表当前的联通的区域个数.
    • 初始化为n(n个点不互相联通,每个点为一个单独的联通区域,所以一共有n个联通区域)每做一次成功的union(把一个点和一个联通区域连接,非联通区域减少了1) count – 1.
  • 读入边: edges[i][0] = v1(边的其中一个点)和edges[i][1] = v2(边的另一个点)
  • find(v1, v2) :读入两个点,判断这两点是是联通的.如果ids[v1] == ids[v2]说明v1和v2是联通的;否则两者不连通
  • union(v1, v2) : 读入一条边的时候,说明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 )

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s

%d bloggers like this: