动态连通性直接听起来会稍微绕口一点,简单的说就是输入一列整数对,其中每个整数都表示某种类型的对象,假设输入的的整数对是p和q,我们可以理解p和q是相连的,假设相连是一种等价关系,一般具有三种特性自反性,对称性,传递性,根据上面的特性,如果整数对不存在某种等价关系,那么直接输出,如果存在就不输出。简单的举几个例子,计算机网络中判断两个计算机是否需要建立新的连接通信,如果可以通过一个或某几个节点能通信,那么我们就不需要建立新的连接,数学中可以将p
和q看成集合,跑题了,看下如何实现的吧,四种方式依次渐进:
p和q做网络上相连可以看成连接,单独的看p和q可以看成触点,可以判断是否存在p和q或者pq之间的等价连接:
@interface DynamicUnion : NSObject @property (strong,nonatomic) NSMutableArray *ids;//存储每个触点对应的值 @property (assign,nonatomic) NSInteger count;//已经连通的连接的数量 -(BOOL)connected:(NSInteger)a secondNumber:(NSInteger)b;//是否已经存在连接或者等价的连接 -(NSInteger)find:(NSInteger)index;//取出触点的值 -(void)dynamicUnion:(NSInteger)a secondNumber:(NSInteger)b;//a,b之间建立一个连接 -(void)initData:(NSInteger)count;//初始化触点的数量 @end
具体实现代码:
-(void)initData:(NSInteger)count{ self.count=count; self.ids=[[NSMutableArray alloc]initWithCapacity:count]; for (NSInteger i=0; i<count; i++) { [self.ids addObject:[NSNumber numberWithInteger:i]]; } } //http://www.cnblogs.com/xiaofeixiang -(BOOL)connected:(NSInteger)a secondNumber:(NSInteger)b{ return [self find:a]==[self find:b]; } -(NSInteger)find:(NSInteger)index{ return [[self.ids objectAtIndex:index] integerValue]; } -(void)dynamicUnion:(NSInteger)a secondNumber:(NSInteger)b{ NSInteger aID=[self find:a]; NSInteger bID=[self find:b]; if (aID==bID) { return; } for (NSInteger i=0;i<[self.ids count]; i++) { if ([[self.ids objectAtIndex:i] integerValue]==aID) { self.ids[i]=[NSNumber numberWithInteger:bID]; } } self.count=self.count-1; }
Quick-Find在Union的过程中,每次都会遍历数组一次,这样有损性能,还是用ids数组存每个触点的值,不过每个值存的意义不一样,我们可以通过ids中的值存储触点的父级,作为一棵树存在,我们就不用遍历ids数组,简单的讲就是4,3的时候ids[4]存值的时候存的是3,这样最后会只要判断根节点就可以。其他方法不用变,我们只需要改变find和dynamicUnion方法即可。
-(NSInteger)find:(NSInteger)index{ while (index!=[[self.ids objectAtIndex:index] integerValue]) { index=[[self.ids objectAtIndex:index] integerValue]; } return index; } //http://www.cnblogs.com/xiaofeixiang -(void)dynamicUnion:(NSInteger)a secondNumber:(NSInteger)b{ NSInteger aRoot=[self find:a]; NSInteger bRoot=[self find:b]; if (aRoot==bRoot) { return; } self.ids[aRoot]=[NSNumber numberWithInteger:bRoot]; self.count--; }
Quick-Union可能会出现一种情况,如果以树的形式去展示的话,最终可能会出现大树的父级别是小树的情况,因为我们需要通过一个权重值,避免出现这种情况,不过我们需要回顾一个树的基础概念。一棵树的大小是它的节点的数量,树中的一个节点的深度是它到根节点的路径上的链接数。输的高度是它的所有节点中的最大深度。加权能保每次find、connected和union都是lgn级别。
//http://www.cnblogs.com/xiaofeixiang @interface DynamicUnionWeight : NSObject @property (strong,nonatomic) NSMutableArray *ids;//存储每个触点对应的值 @property (strong,nonatomic) NSMutableArray *weightArr;//各个根节点对ing的分量的大小 @property (assign,nonatomic) NSInteger count;//已经连通的连接的数量 -(BOOL)connected:(NSInteger)a secondNumber:(NSInteger)b;//是否已经存在连接或者等价的连接 -(NSInteger)find:(NSInteger)index;//取出触点的值 -(void)dynamicUnion:(NSInteger)a secondNumber:(NSInteger)b;//a,b之间建立一个连接 -(void)initData:(NSInteger)count;//初始化触点的数量 @end
具体实现:
-(void)initData:(NSInteger)count{ self.count=count; self.ids=[[NSMutableArray alloc]initWithCapacity:count]; self.weightArr=[[NSMutableArray alloc]initWithCapacity:count]; for (NSInteger i=0; i<count; i++) { [self.ids addObject:[NSNumber numberWithInteger:i]]; [self.weightArr addObject:[NSNumber numberWithInteger:1]]; } } //http://www.cnblogs.com/xiaofeixiang -(BOOL)connected:(NSInteger)a secondNumber:(NSInteger)b{ return [self find:a]==[self find:b]; } -(NSInteger)find:(NSInteger)index{ while (index!=[[self.ids objectAtIndex:index] integerValue]) { index=[[self.ids objectAtIndex:index] integerValue]; } return index; } -(void)dynamicUnion:(NSInteger)a secondNumber:(NSInteger)b{ NSInteger i=[self find:a]; NSInteger j=[self find:b]; if (i==j) { return; } NSInteger weightA=[[self.weightArr objectAtIndex:i] integerValue]; NSInteger weightB=[[self.weightArr objectAtIndex:j] integerValue]; if (weightA<weightB) { self.ids[i]=[NSNumber numberWithInteger:j]; self.weightArr[j]=[NSNumber numberWithInteger:weightA+weightB]; }else{ self.ids[j]=[NSNumber numberWithInteger:i]; self.weightArr[i]=[NSNumber numberWithInteger:weightA+weightB]; } self.count--; }
路径压缩会保证union都接近于1,这个实现只需要加权Quick-Union的算法稍微改动一下,改变一下find即可:
-(NSInteger)find:(NSInteger)index{ while (index!=[[self.ids objectAtIndex:index] integerValue]) { self.ids[index]=self.ids[[self.ids[index] integerValue]]; index=[[self.ids objectAtIndex:index] integerValue]; } return index; } //http://www.cnblogs.com/xiaofeixiang -(void)dynamicUnion:(NSInteger)a secondNumber:(NSInteger)b{ NSInteger i=[self find:a]; NSInteger j=[self find:b]; if (i==j) { return; } NSInteger weightA=[[self.weightArr objectAtIndex:i] integerValue]; NSInteger weightB=[[self.weightArr objectAtIndex:j] integerValue]; if (weightA<weightB) { self.ids[i]=[NSNumber numberWithInteger:j]; self.weightArr[j]=[NSNumber numberWithInteger:weightA+weightB]; }else{ self.ids[j]=[NSNumber numberWithInteger:i]; self.weightArr[i]=[NSNumber numberWithInteger:weightA+weightB]; } self.count--; }
模拟测试:
DynamicUnion *dynamicUnion=[[DynamicUnion alloc]init]; [dynamicUnion initData:10]; NSMutableArray *dataSource=[[NSMutableArray alloc]initWithCapacity:10]; [dataSource addObject:@"4,3"]; [dataSource addObject:@"3,8"]; [dataSource addObject:@"6,5"]; [dataSource addObject:@"9,4"]; [dataSource addObject:@"2,1"]; [dataSource addObject:@"8,9"]; [dataSource addObject:@"5,0"]; [dataSource addObject:@"7,2"]; [dataSource addObject:@"6,1"]; [dataSource addObject:@"1,0"]; for (NSInteger i=0; i<[dataSource count]; i++) { NSString *node=[dataSource objectAtIndex:i]; NSInteger a=[[node substringWithRange:NSMakeRange(0, 1)] integerValue]; NSInteger b=[[node substringWithRange:NSMakeRange(2, 1)] integerValue]; if ([dynamicUnion connected:a secondNumber:b]) { continue; } [dynamicUnion dynamicUnion:a secondNumber:b]; NSLog(@"%ld---%ld",a,b); } NSLog(@"%ld已存在连接",dynamicUnion.count); NSLog(@"iOS技术交流群:228407086"); NSLog(@"原文地址:http://www.cnblogs.com/xiaofeixiang");
结果如下: