动态连通性直接听起来会稍微绕口一点，简单的说就是输入一列整数对，其中每个整数都表示某种类型的对象，假设输入的的整数对是p和q，我们可以理解p和q是相连的，假设相连是一种等价关系，一般具有三种特性自反性，对称性，传递性，根据上面的特性，如果整数对不存在某种等价关系，那么直接输出，如果存在就不输出。简单的举几个例子，计算机网络中判断两个计算机是否需要建立新的连接通信，如果可以通过一个或某几个节点能通信，那么我们就不需要建立新的连接，数学中可以将p和q看成集合，跑题了，看下如何实现的吧，四种方式依次渐进:
Quick-Find算法
p和q做网络上相连可以看成连接，单独的看p和q可以看成触点，可以判断是否存在p和q或者pq之间的等价连接:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
@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
|
具体实现代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
-(
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-Union算法
Quick-Find在Union的过程中，每次都会遍历数组一次，这样有损性能，还是用ids数组存每个触点的值，不过每个值存的意义不一样，我们可以通过ids中的值存储触点的父级，作为一棵树存在，我们就不用遍历ids数组，简单的讲就是4，3的时候ids[4]存值的时候存的是3，这样最后会只要判断根节点就可以。其他方法不用变，我们只需要改变find和dynamicUnion方法即可。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
-(
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算法
Quick-Union可能会出现一种情况，如果以树的形式去展示的话，最终可能会出现大树的父级别是小树的情况，因为我们需要通过一个权重值，避免出现这种情况，不过我们需要回顾一个树的基础概念。一棵树的大小是它的节点的数量，树中的一个节点的深度是它到根节点的路径上的链接数。输的高度是它的所有节点中的最大深度。加权能保每次find、connected和union都是lgn级别。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
//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
|
具体实现:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
-(
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即可:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
-(
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--;
}
|
模拟测试:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
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"
);
|
结果如下:
本文转自Fly_Elephant博客园博客，原文链接：http://www.cnblogs.com/xiaofeixiang/p/4575951.html，如需转载请自行联系原作者
