有向图中包括有向无环图和有向有环图，有向图在任务调度的时候优先级限制是非常有用的，最常见的是大学的排课系统，比如说计算机操作系统的优先级高于高等数学，我们可以用图表示为计算机操作系统→高等数学，高等数学高于线性代数，如果这个时候线性代数的优先级高于计算机操作系统，那么就产生了一个有向环，无法进行排课，课程一般比较多，如果用图表示去判断是否存在环路是比较麻烦的一个事情，所以通常需要判断有向图中是否含有向环。
有向环检测
如果有向图中的某个节点可以按照路径的方向从某个节点开始并返回本身，形成了闭环可以判定是图中含有有向环。有向环中的判定和之前的无向图中的深度搜索类似，如果A→B，在之前图的辅助数据结构我们存储的是所以为A对应的值中含有B，如果索引B中含有值A，即含有有向环。
有向环检测的API跟之前的深度搜索多了一个保存有向环的中节点的数组，和递归需要调用的数组:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
@
interface
DirectedCycle : NSObject
//标记数组
@property (strong,nonatomic) NSMutableArray *marked;
@property (strong,nonatomic) NSMutableArray *cycle;
//有向环中的所有顶点(存在有向环的情况)
@property (strong,nonatomic) NSMutableArray *onStack;
//递归调用的栈上的所有顶点
//从起点到一个顶点的已知路径上的最后一个顶点
@property (strong,nonatomic) NSMutableArray *edgeTo;
@property (assign,nonatomic) Boolean hasCycle;
//初始化
-(instancetype)initWithGraph:(Digraph *)graph;
-(
void
)depthSearch:(Digraph *)graph vertex:(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
77
78
79
|
@implementation DirectedCycle
#pragma mark getter and setter
-(NSMutableArray *)marked{
if
(!_marked) {
_marked=[[NSMutableArray alloc]initWithCapacity:1];
}
return
_marked;
}
-(NSMutableArray *)onStack{
if
(!_onStack) {
_onStack=[[NSMutableArray alloc]initWithCapacity:1];
}
return
_onStack;
}
-(NSMutableArray *)edgeTo{
if
(!_edgeTo) {
_edgeTo=[[NSMutableArray alloc]initWithCapacity:1];
}
return
_edgeTo;
}
-(instancetype)initWithGraph:(Digraph *)graph{
self=[super init];
if
(self) {
for
(NSInteger i=0; i<graph.vertexs;i++) {
[self.onStack addObject:[NSNull
null
]];
[self.edgeTo addObject:[NSNull
null
]];
[self.marked addObject:[NSNull
null
]];
}
//遍历图的顶点
for
(NSInteger s=0; s<graph.vertexs; s++) {
if
(![self isMarked:s]) {
[self depthSearch:graph vertex:s];
}
}
}
return
self;
}
//http://www.cnblogs.com/xiaofeixiang/
-(
void
)depthSearch:(Digraph *)graph vertex:(NSInteger)vertex{
self.onStack[vertex]=[NSNumber numberWithBool:
true
];
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 hasCycle])
return
;
else
if
(![self isMarked:temp]) {
self.edgeTo[temp]=[NSNumber numberWithInteger:vertex];
[self depthSearch:graph vertex:temp];
}
else
if
([self isStack:temp]){
self.cycle=[[NSMutableArray alloc]initWithCapacity:1];
for
(NSInteger i=vertex; i!=temp; i=[self.edgeTo[i] integerValue]) {
[self.cycle insertObject:[NSNumber numberWithInteger:i] atIndex:0];
}
[self.cycle insertObject:[NSNumber numberWithInteger:temp] atIndex:0];
[self.cycle insertObject:[NSNumber numberWithInteger:vertex] atIndex:0];
}
}
self.onStack[vertex]=[NSNumber numberWithBool:
false
];
}
-(Boolean)hasCycle{
return
[self.cycle count]>0;
}
-(Boolean)isMarked:(NSInteger)vertex{
return
self.marked[vertex]==[NSNull
null
]?
false
:[self.marked[vertex] boolValue];
}
-(Boolean)isStack:(NSInteger)vertex{
return
self.onStack[vertex]==[NSNull
null
]?
false
:[self.onStack[vertex] boolValue];
}
@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
|
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];
DirectedCycle *directedCycle=[[DirectedCycle alloc]initWithGraph:graph];
if
([directedCycle.cycle count]) {
NSLog(
@"形成有向环的节点为:%@"
,[directedCycle.cycle componentsJoinedByString:
@"--"
]);
}
NSLog(
@"技术交流群:%@"
,
@"228407086"
);
NSLog(
@"博客园-FlyElephant:http://www.cnblogs.com/xiaofeixiang"
);
|
测试效果:
拓扑排序
拓扑排序能解决我们最开始所说的排课问题，任务调度问题，不过只能对有向无环图(Directed Acyclic Graph简称DAG)进行排序，上面的有向环检测可以作为拓扑排序的一个辅助。拓扑排序在同样可以在深度优先搜索上面进行修改，深度搜索会访问每个顶点刚好一次，可以在深度搜索递归的时候将参数顶点存放在一个数据结构中，遍历数据结构就可以访问图中所有的顶点，遍历的书序取决于调用的的时间，可以在递归之前也可以在递归之后。
通常来说有三种排列顺序:
- 前序:在递归之前加入数组中；
- 后序:在递归之后加入数组中；
- 逆后序:在递归值周加入数组中，不过每次都存放在首位，类似栈;
顶点排序:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
@
interface
DepthFirstOrder : NSObject
//记录顶点是否被标记
@property (strong,nonatomic) NSMutableArray *marked;
@property (strong,nonatomic) NSMutableArray *preQueue;
//所有顶点的前序排列
@property (strong,nonatomic) NSMutableArray *postQueue;
//所有顶点的后序排列
@property (strong,nonatomic) NSMutableArray *reversePostStack;
//所有顶点的逆后序排列
@property (assign,nonatomic) NSInteger count;
//找到与七点vertex所有连通的节点
-(instancetype)initWithGraph:(Digraph *)graph;
-(
void
)depthSearch:(Digraph *)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
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
|
@implementation DepthFirstOrder
#pragma mark getter and setter
-(NSMutableArray *)marked{
if
(!_marked) {
_marked=[[NSMutableArray alloc]initWithCapacity:1];
}
return
_marked;
}
-(NSMutableArray *)preQueue{
if
(!_preQueue) {
_preQueue=[[NSMutableArray alloc]initWithCapacity:1];
}
return
_preQueue;
}
-(NSMutableArray *)postQueue{
if
(!_postQueue) {
_postQueue=[[NSMutableArray alloc]initWithCapacity:1];
}
return
_postQueue;
}
-(NSMutableArray *)reversePostStack{
if
(!_reversePostStack) {
_reversePostStack=[[NSMutableArray alloc]initWithCapacity:1];
}
return
_reversePostStack;
}
-(instancetype)initWithGraph:(Digraph *)graph{
self=[super init];
if
(self) {
for
(NSInteger i=0; i<graph.vertexs;i++) {
[self.marked addObject:[NSNull
null
]];
}
//遍历图的顶点
for
(NSInteger s=0; s<graph.vertexs; s++) {
if
(![self isMarked:s]) {
[self depthSearch:graph vertex:s];
}
}
}
return
self;
}
//http://www.cnblogs.com/xiaofeixiang/
-(
void
)depthSearch:(Digraph *)graph vertex:(NSInteger)vertex{
[self.preQueue addObject:[NSNumber numberWithInteger: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];
}
}
[self.postQueue addObject:[NSNumber numberWithInteger:vertex]];
[self.reversePostStack insertObject:[NSNumber numberWithInteger:vertex] atIndex:0];
}
-(Boolean)isMarked:(NSInteger)vertex{
return
self.marked[vertex]==[NSNull
null
]?
false
:[self.marked[vertex] boolValue];
}
@end
|
有向环检查和顶点排序都是为拓扑排序准备的，拓扑排序只需要调用即可:
|
1
2
3
4
5
6
7
|
@
interface
TopologicalSort : NSObject
@property (strong,nonatomic) NSMutableArray *order;
-(instancetype)initWithDigraph:(Digraph *)graph;
@end
|
实现文件:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
@implementation TopologicalSort
#pragma mark getter and setter
-(NSMutableArray *)order{
if
(!_order) {
_order=[[NSMutableArray alloc]initWithCapacity:1];
}
return
_order;
}
-(instancetype)initWithDigraph:(Digraph *)graph{
self=[super init];
if
(self) {
DirectedCycle *cyclefinder=[[DirectedCycle alloc]initWithGraph:graph];
if
(!cyclefinder.hasCycle) {
DepthFirstOrder *dfs=[[DepthFirstOrder alloc]initWithGraph:graph];
self.order=dfs.reversePostStack;
}
}
return
self;
}
@end
|
我们可以通过下面这幅图检测一下程序的正确性:
测试代码:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
Digraph *digraph=[[Digraph alloc]initWithVertex:13];
[digraph addEdges:0 endVertex:6];
[digraph addEdges:0 endVertex:1];
[digraph addEdges:0 endVertex:5];
[digraph addEdges:2 endVertex:0];
[digraph addEdges:2 endVertex:3];
[digraph addEdges:3 endVertex:5];
[digraph addEdges:5 endVertex:4];
[digraph addEdges:6 endVertex:4];
[digraph addEdges:6 endVertex:9];
[digraph addEdges:7 endVertex:6];
[digraph addEdges:8 endVertex:7];
[digraph addEdges:9 endVertex:10];
[digraph addEdges:9 endVertex:12];
[digraph addEdges:9 endVertex:11];
[digraph addEdges:11 endVertex:12];
TopologicalSort *logicSort=[[TopologicalSort alloc]initWithDigraph:digraph];
for
(NSInteger i=0; i<[logicSort.order count]; i++) {
NSLog(
@"节点%ld"
,[logicSort.order[i] integerValue]);
}
NSLog(
@"技术交流群:%@"
,
@"228407086"
);
NSLog(
@"博客园-FlyElephant:http://www.cnblogs.com/xiaofeixiang"
);
|
测试结果:
如果用节点表示可能会更直接一点，效果如下:
本文转自Fly_Elephant博客园博客，原文链接：http://www.cnblogs.com/xiaofeixiang/p/4713701.html，如需转载请自行联系原作者
![现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int)，已知类QuickSort的quickSort(int[])方法实现了快速排序算法](https://ucc.alicdn.com/b3c447iaqrtq2_20240813_8507e56fc1e0475c88702b767789ed11.png?x-oss-process=image/resize,h_160,m_lfit)