【进阶】6、并查集

2014-03-06 | 阅读：

并查集（Union Find）

一、需求分析

假设有n个村庄，有些村庄之间有连接的路，有些村庄之间并没有连接的路

设计一个数据结构，能够快速执行2个操作
查询2个村庄之间是否有连接的路
连接2个村庄

数组、链表、平衡二叉树、集合（Set）？
查询、连接的时间复杂度都是：O(n)

并查集能够办到查询、连接的均摊时间复杂度都是 O(α(n)) ，α(n) < 5
并查集非常适合解决这类“连接”相关的问题

二、并查集（Union Find）介绍

并查集也叫作不相交集合（Disjoint Set）

并查集有2个核心操作
查找（Find）：查找元素所在的集合（这里的集合并不是特指Set这种数据结构，是指广义的数据集合）
合并（Union）：将两个元素所在的集合合并为一个集合

有2种常见的实现思路

1、Quick Find
✓ 查找（Find）的时间复杂度：O(1)
✓ 合并（Union）的时间复杂度：O(n)

2、Quick Union
✓ 查找（Find）的时间复杂度：O(logn)，可以优化至 O(α(n)) ，α(n) < 5
✓ 合并（Union）的时间复杂度：O(logn)，可以优化至 O(α(n)) ，α(n) < 5

三、如何存储数据

假设并查集处理的数据都是整型，那么可以用整型数组来存储数据

不难看出
0、1、3 属于同一集合
2 单独属于一个集合
4、5、6、7 属于同一集合

因此，并查集是可以用数组实现的树形结构（二叉堆、优先级队列也是可以用数组实现的树形结构）

并查集（Union Find）实现

一、接口定义

/// 检查v1、v2是否属于同一个集合
/// @param v1 元素v1
/// @param v2 元素v2
-(BOOL)isSameWithV1:(int)v1 v2:(int)v2;


/// 查找v所属的集合，返回根节点
/// @param v 元素v
-(int)findV:(int)v;


/// 合并v1、v2所属的集合
/// @param v1 元素v1
/// @param v2 元素v2
-(void)unionWithV1:(int)v1 v2:(int)v2;

二、初始化

初始化时，每个元素各自属于一个单元素集合

/// 初始化一个并查集
/// @param capacity 容量
-(instancetype)initWithCapacity:(int)capacity{
    
    self = [super init];
    if (self) {
        self.parents = [NSMutableArray arrayWithCapacity:capacity];
        for (int i = 0; i<capacity; i++) {
            self.parents[i] = @(i);
        }
    }
    return self;
}

三、Quick Find

1、Quick Find - union

Quick Find 的 union(v1, v2)：让 v1 所在集合的所有元素都指向 v2 的根节点

2、Quick Find - Find

◼ find(0) == 2
◼ find(1) == 2
◼ find(3) == 4
◼ find(2) == 2

3、代码实现

/// 检查v1、v2是否属于同一个集合
/// @param v1 元素v1
/// @param v2 元素v2
-(BOOL)isSameWithV1:(int)v1 v2:(int)v2{
    return [self findV:v1] == [self findV:v2];
}

//时间复杂度：O(1)
-(int)findV:(int)v{
    [self rangeCheck:v];
    
    /**
    * 父节点就是根节点
    */
    return [self.parents[v] intValue];
}


//时间复杂度：O(n)
-(void)unionWithV1:(int)v1 v2:(int)v2{
    int p1 = [self findV:v1];
    int p2 = [self findV:v2];
    if(p1 == p2) return;
    
    /**
    * 将v1所在集合的所有元素，都嫁接到v2的父节点上
    */
    for (int i = 0; i<self.parents.count; i++) {
        if (p1 == [self.parents[i] intValue]) {
            self.parents[i] = @(p2);
        }
    }
}

四、Quick Union

1、Quick Union - union

Quick Union 的 union(v1, v2)：让 v1 的根节点指向 v2 的根节点

2、Quick Union - find

◼ find(0) == 2
◼ find(1) == 2
◼ find(3) == 2
◼ find(2) == 2

3、代码实现

/**
 * 通过parent链条不断地向上找，直到找到根节点
 * 时间复杂度：O(logn)

 */
-(int)findV:(int)v{
    [self rangeCheck:v];
    while (v != [self.parents[v] intValue]) {
        v = [self.parents[v] intValue];
    }
    return v;
}



/**
 * 将v1的根节点嫁接到v2的根节点上
 * 时间复杂度：O(logn)
 */
-(void)unionWithV1:(int)v1 v2:(int)v2{
    int p1 = [self findV:v1];
    int p2 = [self findV:v2];
    if(p1 == p2) return;
    self.parents[p1] = @(p2);
}

并查集（Union Find）优化

在Union的过程中，可能会出现树不平衡的情况，甚至退化成链表

有2种常见的优化方案
基于size的优化：元素少的树嫁接到元素多的树
基于rank的优化：矮的树嫁接到高的树

一、QuickUnion_Size优化

-(instancetype)initWithCapacity:(int)capacity{
    self = [super initWithCapacity:capacity];
    if (self) {
        //存放根节点对应集合的元素数量
        self.sizes = [NSMutableArray arrayWithCapacity:capacity];
        for (int i= 0; i<capacity; i++) {
            //初始化时数量为1
            self.sizes[i] = @(1);
        }
    }
    return self;
}

-(int)findV:(int)v{
    [self rangeCheck:v];
    while (v != [self.parents[v] intValue]) {
        v = [self.parents[v] intValue];
    }
    return v;
}



//基于size的优化：数量比较少的嫁接到数量比较多的 尽量保持树的平衡
-(void)unionWithV1:(int)v1 v2:(int)v2{
    int p1 = [self findV:v1];
    int p2 = [self findV:v2];
    if (p1 == p2) return;
    
    
    //数量比较少的嫁接到数量比较多的 尽量保持树的平衡
    int p1Size = [self.sizes[p1] intValue];
    int p2Size = [self.sizes[p2] intValue];
    if (p1Size < p2Size) {
        //p1 合并到 p2
        self.parents[p1] = @(p2);
        
        //更新p2节点所在集合的元素数量
        self.sizes[p2] = @(p1Size + p2Size);
    }else{
        //p2 合并到 p1
        self.parents[p2] = @(p1);
        
        //更新p1节点所在集合的元素数量
        self.sizes[p1] = @(p1Size + p2Size);
    }
}

二、QuickUnion_Rank优化

基于size的优化，也可能会存在树不平衡的问题

基于rank的优化

-(instancetype)initWithCapacity:(int)capacity{
    self = [super initWithCapacity:capacity];
    if (self) {
        //存放根节点对应结合的树的高度
        self.ranks = [NSMutableArray arrayWithCapacity:capacity];
        for (int i = 0; i<capacity; i++) {
            //初始化时高度为1
            self.ranks[i] = @(1);
        }
    }
    return self;
}

-(int)findV:(int)v{
    [self rangeCheck:v];
    while (v != [self.parents[v] intValue]) {
        v = [self.parents[v] intValue];
    }
    return v;
}


//基于rank的优化：高度比较少的嫁接到高度比较多的 保持树的平衡
-(void)unionWithV1:(int)v1 v2:(int)v2{
    int p1 = [self findV:v1];
    int p2 = [self findV:v2];
    if (p1 == p2) return;
    
    int p1Rank = [self.ranks[p1] intValue];
    int p2Rank = [self.ranks[p2] intValue];
    
    if (p1Rank < p2Rank) {
        self.parents[p1] = @(p2);
        //不需要更新树的高度
    }else if(p2Rank < p1Rank){
        self.parents[p2] =@(p1);
        //不需要更新树的高度
    }else{
        //相等时，谁合并谁都可以，采用v1 合并到 v2
        self.parents[p1] = @(p2);
        
        //更新p2Rank的高度
        self.ranks[p2] = @(p2Rank+1);
    }
}

三、QuickUnion_Rank_PathCompression优化

//基于 QuickUnion_Rank_PathCompression(路径压缩) 的优化
-(int)findV:(int)v{
    [self rangeCheck:v];
    
    
    int parent =  [self.parents[v] intValue];
    if (v != parent) {
        /**
         会一路找到根节点，并将沿途节点的父节点都赋值为根节点
         
         比如：1->4->8->10
         
         find:4
         1->4->10
            8->10
         
         find:1
         1->10
         4->10
         8->10
         
         
         存在的问题：有一定的性能开销
         */
        self.parents[v] = @([self findV:parent]);
    }
    return [self.parents[v] intValue];
}

路径压缩使路径上的所有节点都指向根节点，所以实现成本稍高

还有2种更优的做法，不但能降低树高，实现成本也比路径压缩低
路径分裂（Path Spliting）
路径减半（Path Halving）
路径分裂、路径减半的效率差不多，但都比路径压缩要好

四、QuickUnion_Rank_PathSplitting优化

路径分裂：使路径上的每个节点都指向其祖父节点（parent的parent）

//基于 QuickUnion_Rank_PathSplitting(路径分裂) 的优化
-(int)findV:(int)v{
    [self rangeCheck:v];
    
    while (v!= [self.parents[v] intValue]) {
        
        int parent =  [self.parents[v] intValue];
        int grand = [self.parents[parent] intValue];
        
        //将v的父节点变为其祖父节点
        self.parents[v] = @(grand);
        
        //下轮查看其父节点
        v = parent;
    }
   
    return v;
}

五、QuickUnion_Rank_PathHalving优化

路径减半：使路径上每隔一个节点就指向其祖父节点（parent的parent）

//基于 QuickUnion_Rank_PathHalving(路径减半) 的优化
-(int)findV:(int)v{
    [self rangeCheck:v];
    
    while (v != [self.parents[v] intValue]) {
        int parent =  [self.parents[v] intValue];
        int grand = [self.parents[parent] intValue];
        
        //将v的父节点变为其祖父节点
        self.parents[v] = @(grand);
        
        //下轮查看其祖父节点
        v = grand;
    }
   
    return v;
}

总结

摘自《维基百科》： https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Time_complexity

大概意思是使用路径压缩、分裂或减半 + 基于rank或者size的优化
✓ 可以确保每个操作的均摊时间复杂度为 O(𝛼(𝑛)) ，α(𝑛) < 5

个人建议的搭配
✓ Quick Union
✓ 基于 rank 的优化
✓ Path Halving 或 Path Spliting

关于自定义类型

之前的使用都是基于整型数据，如果其他自定义类型也想使用并查集呢？

方案一：通过一些方法将自定义类型转为整型后使用并查集（比如生成哈希值）
方案二：使用链表+映射(Map)

@interface LCGenericUnionFind : NSObject

/// 设置一个集合元素
/// @param v 元素
-(void)makeSet:(id)v;


/// 查找v所属的集合，返回根节点
/// @param v 元素v
-(id)findV:(id)v;


/// 检查v1、v2是否属于同一个集合
/// @param v1 元素v1
/// @param v2 元素v2
-(BOOL)isSameWithV1:(id)v1 v2:(id)v2;


/// 合并v1、v2所属的集合
/// @param v1 元素v1
/// @param v2 元素v2
-(void)unionWithV1:(id)v1 v2:(id)v2;

@end

#import "LCGenericUnionFind.h"



#pragma mark - LCUFNode

@interface LCUFNode : NSObject
@property(nonatomic,strong)id           value;  //value
@property(nonatomic,strong)LCUFNode *   parent; //父节点
@property(nonatomic,assign)int          rank;   //节点高度
@end;


@implementation LCUFNode

-(instancetype)init{
    if (self = [super init]) {
        self.parent = self;
        self.rank = 1;
    }
    return self;
}


-(instancetype)initWithValue:(id)value{
    if(self = [self init]){
         self.value = value;
    }
    return self;
}
@end



#pragma mark - LCGenericUnionFind

@interface LCGenericUnionFind()
@property(nonatomic,strong)NSMutableDictionary * nodes;
@end


@implementation LCGenericUnionFind

-(NSMutableDictionary *)nodes{
    if (_nodes == nil) {
        _nodes = [NSMutableDictionary dictionary];
    }
    return _nodes;
}

//v:node,放入nodes
-(void)makeSet:(id)v{
    if ([self __nodesGet:v]) return;
    LCUFNode * node = [[LCUFNode alloc] initWithValue:v];
    [self __nodesPutKey:v value:node];
}



/// 查找v所属的集合，返回根节点
/// @param v 元素v
-(id)findV:(id)v{
    LCUFNode * rootNode = [self __findRootNodeV:v];
    return rootNode?rootNode.value:nil;
}



/// 检查v1、v2是否属于同一个集合
/// @param v1 元素v1
/// @param v2 元素v2
-(BOOL)isSameWithV1:(id)v1 v2:(id)v2{
    return [[self findV:v1] isEqual:[self findV:v2]];
}




/// 合并v1、v2所属的集合
/// @param v1 元素v1
/// @param v2 元素v2
-(void)unionWithV1:(id)v1 v2:(id)v2{
    
    LCUFNode* v1Root = [self __findRootNodeV:v1];
    LCUFNode* v2Root = [self __findRootNodeV:v2];
    
    if ([v1Root isEqual:v2Root]) return;
    
    if (v1Root.rank < v2Root.rank) {
        v1Root.parent = v2Root;
    }else if(v2Root.rank < v1Root.rank){
        v2Root.parent = v1Root;
    }else{
        v1Root.parent = v2Root;
        v2Root.rank +=1;
    }
}


                      
#pragma mark - 内部方法
                      
                      
-(id)__nodesGet:(id)key{
    NSString * keyHash = [NSString stringWithFormat:@"%ld",[key hash]];
    return  [self.nodes objectForKey:keyHash];
}

-(void)__nodesPutKey:(id)key value:(id)value{
    NSString * keyHash = [NSString stringWithFormat:@"%ld",[key hash]];
    [self.nodes setObject:value forKey:keyHash];
}
                

-(LCUFNode*)__findRootNodeV:(id)v{
    
    LCUFNode * node = [self __nodesGet:v];
    if (node == nil) return nil;
    
    while (![node isEqual:node.parent]) {
        node = node.parent;
    }
    
    return node;
}

@end

使用示例：

-(void)test9_2{
    
    LCGenericUnionFind * unionFind = [[LCGenericUnionFind alloc] init];
    
    NSObject * obj1 = [[NSObject alloc] init];
    NSObject * obj2 = [[NSObject alloc] init];
    NSObject * obj3 = [[NSObject alloc] init];
    NSObject * obj4 = [[NSObject alloc] init];
    
    
    [unionFind makeSet:obj1];
    [unionFind makeSet:obj2];
    [unionFind makeSet:obj3];
    [unionFind makeSet:obj4];
    [unionFind unionWithV1:obj1 v2:obj2];
    [unionFind unionWithV1:obj1 v2:obj3];
    [unionFind unionWithV1:obj1 v2:obj4];
    
    [LCAssert AssertWithValue:[unionFind isSameWithV1:obj2 v2:obj4]];

    
    NSObject * obj5 = [[NSObject alloc] init];
    NSObject * obj6 = [[NSObject alloc] init];
    [unionFind makeSet:obj5];
    [unionFind makeSet:obj6];
    [unionFind unionWithV1:obj5 v2:obj6];
    [LCAssert AssertWithValue:[unionFind isSameWithV1:obj5 v2:obj6]];
    [LCAssert AssertWithValue:![unionFind isSameWithV1:obj3 v2:obj6]];
    [unionFind unionWithV1:obj2 v2:obj6];
    [LCAssert AssertWithValue:[unionFind isSameWithV1:obj1 v2:obj6]];


    
    NSObject * obj7 = [[NSObject alloc] init];
    NSObject * obj8 = [[NSObject alloc] init];
    [unionFind makeSet:obj7];
    [unionFind makeSet:obj8];
    [unionFind unionWithV1:obj7 v2:obj8];
    [LCAssert AssertWithValue:[unionFind isSameWithV1:obj7 v2:obj8]];
    [LCAssert AssertWithValue:![unionFind isSameWithV1:obj1 v2:obj8]];
    [unionFind unionWithV1:obj5 v2:obj8];
    [LCAssert AssertWithValue:[unionFind isSameWithV1:obj1 v2:obj8]];
}

行者常至，为者常成！

JHHK