图中最常用到的两种搜索深度优先搜索和广度优先搜索，深度优先搜索是一种在开发爬虫早期使用较多的方法它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链接的Html文件) ，广度搜索属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
深度优先搜索
图中我们经常会遇到一个问题就是图的连通性，比如说从一个顶点到另外一个顶点，判断顶点和其他顶点之间的连通性，以下图为例:
搜索API定义:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
@
interface
DepthFirstSearch : NSObject
//记录顶点是否被标记
@property (strong,nonatomic) NSMutableArray *marked;
@property (assign,nonatomic) NSInteger count;
//找到与七点vertex所有连通的节点
-(instancetype)initWithGraphAndVertex:(Graph *)graph vertex:(NSInteger)vertex;
-(
void
)depthSearch:(Graph *)graph vertex:(NSInteger)vertex;
//节点是否被标记
-(Boolean)isMarked:(NSInteger)vertex;
@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
|
@implementation DepthFirstSearch
#pragma mark getter and setter
-(NSMutableArray *)marked{
if
(!_marked) {
_marked=[[NSMutableArray alloc]initWithCapacity:1];
}
return
_marked;
}
-(instancetype)initWithGraphAndVertex:(Graph *)graph vertex:(NSInteger)vertex{
self=[super init];
if
(self) {
for
(NSInteger i=0; i<graph.vertexs;i++) {
[self.marked addObject:[NSNull
null
]];
}
[self depthSearch:graph vertex:vertex];
}
return
self;
}
//http://www.cnblogs.com/xiaofeixiang/
-(
void
)depthSearch:(Graph *)graph vertex:(NSInteger)vertex{
self.marked[vertex]=[NSNumber numberWithBool:
true
];
self.count++;
for
(NSInteger i=0; i<[graph.adjDataSource[vertex] count]; i++) {
NSInteger temp=[[graph.adjDataSource[vertex] objectAtIndex:i] integerValue];
if
(![self isMarked:temp]) {
[self depthSearch:graph vertex:temp];
}
}
}
-(Boolean)isMarked:(NSInteger)vertex{
return
self.marked[vertex]==[NSNull
null
]?
false
:[self.marked[vertex] boolValue];
}
@end
|
代码测试:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
Graph *graph=[[Graph alloc]initWithVertex:6];
[graph addEdges:0 endVertex:5];
[graph addEdges:2 endVertex:4];
[graph addEdges:2 endVertex:3];
[graph addEdges:1 endVertex:2];
[graph addEdges:0 endVertex:1];
[graph addEdges:3 endVertex:4];
[graph addEdges:5 endVertex:3];
[graph addEdges:0 endVertex:2];
DepthFirstSearch *search=[[DepthFirstSearch alloc]initWithGraphAndVertex:graph vertex:0];
for
(NSInteger i=0; i<graph.vertexs; i++) {
NSLog(
@"节点%ld--值为:%@"
,i,search.marked[i]);
}
NSLog(
@"技术交流群:%@"
,
@"228407086"
);
NSLog(
@"原文地址:http://www.cnblogs.com/xiaofeixiang"
);
|
测试效果:
1表示连通，节点0和其他节点直接都可以直接连通，我们通过递归的方式成功的判断亮点之间的连通性，顶点直接的连通性是通过边链接的，深度搜索将在此方法上改动然后给出单点之间的路径，注意是路径不是最短路径，我们会发现代码变动很小。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
//深度优先
@
interface
DepthFirstPath : NSObject
//记录顶点是否被标记
@property (strong,nonatomic) NSMutableArray *marked;
//起点
@property (assign,nonatomic) NSInteger beginVertex;
//从起点到一个顶点的已知路径上的最后一个顶点
@property (strong,nonatomic) NSMutableArray *edgeTo;
@property (assign,nonatomic) NSInteger count;
//找到与七点vertex所有连通的节点
-(instancetype)initWithGraphAndVertex:(Graph *)graph vertex:(NSInteger)vertex;
-(
void
)depthSearch:(Graph *)graph vertex:(NSInteger)vertex;
-(NSMutableArray *)pathTo:(NSInteger)vertex;
//节点是否被标记
-(Boolean)hasPathTo:(NSInteger)vertex;
@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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
@implementation DepthFirstPath
#pragma mark getter and setter
-(NSMutableArray *)marked{
if
(!_marked) {
_marked=[[NSMutableArray alloc]initWithCapacity:1];
}
return
_marked;
}
-(NSMutableArray *)edgeTo{
if
(!_edgeTo) {
_edgeTo=[[NSMutableArray alloc]initWithCapacity:1];
}
return
_edgeTo;
}
-(instancetype)initWithGraphAndVertex:(Graph *)graph vertex:(NSInteger)vertex{
self=[super init];
if
(self) {
for
(NSInteger i=0; i<graph.vertexs;i++) {
[self.marked addObject:[NSNull
null
]];
[self.edgeTo addObject:[NSNull
null
]];
}
self.beginVertex=vertex;
[self depthSearch:graph vertex:vertex];
}
return
self;
}
//http://www.cnblogs.com/xiaofeixiang
-(
void
)depthSearch:(Graph *)graph vertex:(NSInteger)vertex{
self.marked[vertex]=[NSNumber numberWithBool:
true
];
self.count++;
for
(NSInteger i=0; i<[graph.adjDataSource[vertex] count]; i++) {
NSInteger temp=[[graph.adjDataSource[vertex] objectAtIndex:i] integerValue];
if
(![self hasPathTo:temp]) {
self.edgeTo[temp]=[NSNumber numberWithInteger:vertex];
[self depthSearch:graph vertex:temp];
}
}
}
-(Boolean)hasPathTo:(NSInteger)vertex{
return
self.marked[vertex]==[NSNull
null
]?
false
:[self.marked[vertex] boolValue];
}
-(NSMutableArray *)pathTo:(NSInteger)vertex{
if
(![self hasPathTo:vertex]) {
return
NULL;
}
NSMutableArray *path=[[NSMutableArray alloc]initWithCapacity:1];
for
(NSInteger i=vertex; i!=self.beginVertex; i=[self.edgeTo[i] integerValue]) {
[path insertObject:[NSNumber numberWithInteger:i] atIndex:0];
}
[path insertObject:[NSNumber numberWithInteger:self.beginVertex] atIndex:0];
return
path;
}
@end
|
代码中我们多了一个edgeTo数组记录当前索引顶点的最后一个顶点，当edgeTo[1]=2表示顶点1和顶点2之间是直接相连，最后输出路径的时候利用栈的特性，先进后出，输出正确路径，测试代码如下:
|
1
2
3
4
5
6
7
8
9
10
11
|
NSInteger beginVertex=0;
DepthFirstPath *path=[[DepthFirstPath alloc]initWithGraphAndVertex:graph vertex:beginVertex];
for
(NSInteger i=0; i<[path.edgeTo count]; i++) {
NSLog(
@"节点%ld--值为:%@"
,i,path.edgeTo[i]);
}
for
(NSInteger i=0; i<graph.vertexs;i++) {
NSMutableArray *data=[path pathTo:i];
NSLog(
@"%ld到%ld路径为:%@"
,beginVertex,i,[data componentsJoinedByString:
@"--"
]);
}
NSLog(
@"技术交流群:%@"
,
@"228407086"
);
NSLog(
@"原文地址:http://www.cnblogs.com/xiaofeixiang"
);
|
测试效果:
广度优先搜索
如果我们仔细观察会发现一个现象，图片中我们很明显看到顶点0可以直接到5，我们确发现广度搜索的路径给出的是0-2-3-5，如果想要获取最短路径，界限来一起看一下广度优先搜索，代码与上面的代码也是改动了一部分，比较好懂，代码如下:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
@
interface
BreadthFirstPath : NSObject
//记录顶点是否被标记
@property (strong,nonatomic) NSMutableArray *marked;
//起点
@property (assign,nonatomic) NSInteger beginVertex;
//从起点到一个顶点的已知路径上的最后一个顶点
@property (strong,nonatomic) NSMutableArray *edgeTo;
//找到与七点vertex所有连通的节点
-(instancetype)initWithGraphAndVertex:(Graph *)graph vertex:(NSInteger)vertex;
-(
void
)breadthSearch:(Graph *)graph vertex:(NSInteger)vertex;
-(NSMutableArray *)pathTo:(NSInteger)vertex;
//节点是否被标记
-(Boolean)hasPathTo:(NSInteger)vertex;
@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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
@implementation BreadthFirstPath
#pragma mark getter and setter
-(NSMutableArray *)marked{
if
(!_marked) {
_marked=[[NSMutableArray alloc]initWithCapacity:1];
}
return
_marked;
}
-(NSMutableArray *)edgeTo{
if
(!_edgeTo) {
_edgeTo=[[NSMutableArray alloc]initWithCapacity:1];
}
return
_edgeTo;
}
-(instancetype)initWithGraphAndVertex:(Graph *)graph vertex:(NSInteger)vertex{
self=[super init];
if
(self) {
for
(NSInteger i=0; i<graph.vertexs;i++) {
[self.marked addObject:[NSNull
null
]];
[self.edgeTo addObject:[NSNull
null
]];
}
self.beginVertex=vertex;
[self breadthSearch:graph vertex:vertex];
}
return
self;
}
//http://www.cnblogs.com/xiaofeixiang
-(
void
)breadthSearch:(Graph *)graph vertex:(NSInteger)vertex{
NSMutableArray *queue=[[NSMutableArray alloc]initWithCapacity:1];
self.marked[vertex]=[NSNumber numberWithBool:
true
];
[queue addObject:[NSNumber numberWithInteger:vertex]];
while
([queue count]>0) {
NSInteger header=[[queue objectAtIndex:0] integerValue];
[queue removeObjectAtIndex:0];
for
(NSInteger i=0; i<[graph.adjDataSource[header] count]; i++) {
NSInteger temp=[[graph.adjDataSource[header] objectAtIndex:i] integerValue];
if
(![self isMarked:temp]) {
self.marked[temp]=[NSNumber numberWithBool:
true
];
self.edgeTo[temp]=[NSNumber numberWithInteger:header];
[queue addObject:[NSNumber numberWithInteger:temp]];
}
}
}
}
-(Boolean)isMarked:(NSInteger)vertex{
return
self.marked[vertex]==[NSNull
null
]?
false
:[self.marked[vertex] boolValue];
}
-(Boolean)hasPathTo:(NSInteger)vertex{
return
self.marked[vertex]==[NSNull
null
]?
false
:[self.marked[vertex] boolValue];
}
-(NSMutableArray *)pathTo:(NSInteger)vertex{
if
(![self hasPathTo:vertex]) {
return
NULL;
}
NSMutableArray *path=[[NSMutableArray alloc]initWithCapacity:1];
for
(NSInteger i=vertex; i!=self.beginVertex; i=[self.edgeTo[i] integerValue]) {
[path insertObject:[NSNumber numberWithInteger:i] atIndex:0];
}
[path insertObject:[NSNumber numberWithInteger:self.beginVertex] atIndex:0];
return
path;
}
@end
|
测试代码:
|
1
2
3
4
5
6
7
8
9
10
11
12
|
NSInteger beginVertex=0;
BreadthFirstPath *breadthPath=[[BreadthFirstPath alloc]initWithGraphAndVertex:graph vertex:beginVertex];
for
(NSInteger i=0; i<[breadthPath.edgeTo count]; i++) {
NSLog(
@"节点%ld--值为:%@"
,i,breadthPath.edgeTo[i]);
}
for
(NSInteger i=0; i<graph.vertexs;i++) {
NSMutableArray *data=[breadthPath pathTo:i];
NSLog(
@"%ld到%ld路径为:%@"
,beginVertex,i,[data componentsJoinedByString:
@"--"
]);
}
NSLog(
@"技术交流群:%@"
,
@"228407086"
);
NSLog(
@"原文地址:http://www.cnblogs.com/xiaofeixiang"
);
|
测试效果:
本文转自Fly_Elephant博客园博客，原文链接：http://www.cnblogs.com/xiaofeixiang/p/4696971.html，如需转载请自行联系原作者
