图是由顶点和边连接而成，如果边是没有方向的是就是之前文章中说的无向图，关于无向图可以参考本人之前的文章，如果边是有方向的，则称之为有向图。从顶点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，如需转载请自行联系原作者
