算法-有向图及可达性
图是由顶点和边连接而成，如果边是没有方向的是就是之前文章中说的无向图，关于无向图可以参考本人之前的文章，如果边是有方向的，则称之为有向图。从顶点A→B，我们可以理解为A到B可达，有向图和无向图一样通过邻接表保存每一条边，由于边是有方向的，因此在添加边的过程中只需要添加一条边即可。关于可达性一个节点数组的可达性，采用的方法是之前的深度优先搜索一样的代码，通过递归将标记位Bool标记位判断数组中每个顶点的可达性。为了测试，选择下面一张有向图:
有向图基础
通过图片我们可以发现图中有13个节点，22条边，顶点0指出的节点有1，5，指入的节点有2，6，我们先实现所有顶点指出的节点，之后可以通过反转判断所有节点的指入节点：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
@interface Digraph : NSObject
//顶点的总数@property (assign,nonatomic) NSInteger vertexs;//边的数总数@property (assign,nonatomic) NSInteger edges;//连接点的边@property (strong,nonatomic) NSMutableArray *adjDataSource;-(instancetype)initWithVertex:(NSInteger)vertexs;//添加一条有向边 startVertex→endVertex-(void)addEdges:(NSInteger)startVertex endVertex:(NSInteger)endVertex;
-(Digraph *)reverse;//该图的反向图
@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
|
@implementation Digraph-(instancetype)initWithVertex:(NSInteger)vertexs{ self=[super init];
if (self) {
self.vertexs=vertexs;
for (NSInteger i=0; i<vertexs; i++) {
NSMutableArray *neighbourVertex=[[NSMutableArray alloc]initWithCapacity:1];
[self.adjDataSource addObject:neighbourVertex];//创建邻接表,将所有链表初始化为空
}
}
return self;
}//http://www.cnblogs.com/xiaofeixiang-(void)addEdges:(NSInteger)startVertex endVertex:(NSInteger)endVertex{
//将endVertex添加到startVertex的链表中
[self.adjDataSource[startVertex] insertObject:[NSNumber numberWithInteger:endVertex] atIndex:0];
self.edges=self.edges+1;
}-(Digraph *)reverse{ Digraph *digraph=[[Digraph alloc]initWithVertex:self.vertexs];
for (NSInteger i=0; i<self.vertexs; i++) {
NSMutableArray *tempArr=self.adjDataSource[i];
for (NSInteger j=0; j<[tempArr count]; j++) {
[digraph addEdges:[tempArr[j] integerValue] endVertex:i];
}
}
return digraph;
}#pragma mark getter and setter-(NSMutableArray *)adjDataSource{ if (!_adjDataSource) {
_adjDataSource=[[NSMutableArray alloc]initWithCapacity:1];
}
return _adjDataSource;
}@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
|
Digraph *graph=[[Digraph alloc]initWithVertex:13];[graph addEdges:4 endVertex:2];[graph addEdges:2 endVertex:3];[graph addEdges:3 endVertex:2];[graph addEdges:6 endVertex:0];[graph addEdges:0 endVertex:1];[graph addEdges:2 endVertex:0];[graph addEdges:11 endVertex:12];[graph addEdges:12 endVertex:9];[graph addEdges:9 endVertex:10];[graph addEdges:9 endVertex:11];[graph addEdges:8 endVertex:9];[graph addEdges:10 endVertex:12];[graph addEdges:11 endVertex:4];[graph addEdges:4 endVertex:3];[graph addEdges:3 endVertex:5];[graph addEdges:7 endVertex:8];[graph addEdges:8 endVertex:7];[graph addEdges:5 endVertex:4];[graph addEdges:0 endVertex:5];[graph addEdges:6 endVertex:4];[graph addEdges:6 endVertex:9];[graph addEdges:7 endVertex:6];for (NSInteger i=0; i<[graph.adjDataSource count]; i++) {
NSLog(@"节点%ld指出→的节点:%@",i,[graph.adjDataSource[i] componentsJoinedByString:@"--"]);
}NSLog(@"技术交流群:%@",@"228407086");
NSLog(@"原文地址:http://www.cnblogs.com/xiaofeixiang");
|
测试效果:
现在可以判断出顶点的指出节点，实现文件中有一个reverse方法将图反转，求出顶点的转入节点:
|
1
2
3
4
5
6
|
Digraph *digraph=[graph reverse];for (NSInteger i=0; i<[digraph.adjDataSource count]; i++) {
NSLog(@"指入%ld⬅️的节点:%@",i,[digraph.adjDataSource[i] componentsJoinedByString:@"--"]);
}NSLog(@"技术交流群:%@",@"228407086");
NSLog(@"原文地址:http://www.cnblogs.com/xiaofeixiang");
|
测试效果:
可达性
可达性的判断和之前的深度优先搜索基本没变化，先来看一下需要实现的方法:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
@interface DirectedDFS : NSObject
//标记数组@property (strong,nonatomic) NSMutableArray *marked;//找到arr中顶点可达的所有顶点-(instancetype)initDirectedDFSWithVertex:(Digraph *)graph vertexArr:(NSArray *)arr;//在graph中找到从vertex可达的所有顶点-(void)directedDFS:(Digraph *)graph vertex:(NSInteger)vertex;
//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
38
39
40
41
42
|
@implementation DirectedDFS#pragma mark getter and setter-(NSMutableArray *)marked{ if (!_marked) {
_marked=[[NSMutableArray alloc]initWithCapacity:1];
}
return _marked;
}-(instancetype)initDirectedDFSWithVertex:(Digraph *)graph vertexArr:(NSArray *)arr{ self=[super init];
if (self) {
for (NSInteger i=0; i<graph.vertexs;i++) {
[self.marked addObject:[NSNull null]];
}
//遍历有向图中的顶点
for (NSInteger j=0; j<[arr count]; j++) {
if (![self isMarked:[arr[j] integerValue]]) {
[self directedDFS:graph vertex:[arr[j] integerValue]];
}
}
}
return self;
}//博客园-FlyElephant:http://www.cnblogs.com/xiaofeixiang/-(void)directedDFS:(Digraph *)graph vertex:(NSInteger)vertex{
self.marked[vertex]=[NSNumber numberWithBool:true];
for (NSInteger i=0; i<[graph.adjDataSource[vertex] count]; i++) {
NSInteger temp=[[graph.adjDataSource[vertex] objectAtIndex:i] integerValue];
if (![self isMarked:temp]) {
[self directedDFS: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
|
NSArray *sources=[NSArray arrayWithObjects:@"2", nil];
DirectedDFS *directedDFS=[[DirectedDFS alloc]initDirectedDFSWithVertex:graph vertexArr:sources];NSMutableArray *reachableArr=[[NSMutableArray alloc]initWithCapacity:1];for (NSInteger i=0; i<graph.vertexs; i++) {
if (directedDFS.marked[i]&&directedDFS.marked[i]!=[NSNull null]) {
[reachableArr addObject:[NSNumber numberWithInteger:i]];
}
}NSLog(@"可达的节点:%@",[reachableArr componentsJoinedByString:@"--"]);
NSLog(@"技术交流群:%@",@"228407086");
NSLog(@"博客园-FlyElephant:http://www.cnblogs.com/xiaofeixiang");
|
测试效果:
本文转自Fly_Elephant博客园博客，原文链接：http://www.cnblogs.com/xiaofeixiang/p/4703980.html，如需转载请自行联系原作者