算法-有向环和拓扑排序
本文共 8844 字，大约阅读时间需要 29 分钟。
有向图中包括有向无环图和有向有环图，有向图在任务调度的时候优先级限制是非常有用的，最常见的是大学的排课系统，比如说计算机操作系统的优先级高于高等数学，我们可以用图表示为计算机操作系统→高等数学，高等数学高于线性代数，如果这个时候线性代数的优先级高于计算机操作系统，那么就产生了一个有向环，无法进行排课，课程一般比较多，如果用图表示去判断是否存在环路是比较麻烦的一个事情，所以通常需要判断有向图中是否含有向环。
有向环检测
如果有向图中的某个节点可以按照路径的方向从某个节点开始并返回本身，形成了闭环可以判定是图中含有有向环。有向环中的判定和之前的无向图中的深度搜索类似，如果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，如需转载请自行联系原作者
你可能感兴趣的文章
Python 数据库备份脚本（邮件通知）
查看>>
学习SDL的一些资料（整理）
查看>>
[动态库]深入分析Windows和Linux动态库应用异同
查看>>
Linux下查看CPU信息、机器型号等硬件信息命令
查看>>
Lync Server 2013 部署 _ 部署简介及系统要求
查看>>
前端小随笔
查看>>
view属性大全
查看>>
Java文件编码示例
查看>>
CactiFans V1.0中文版发布
查看>>
HTML如何显示小于号“<”等特殊符号？
查看>>
别伤了虚拟桌面管理员的"心"
查看>>
Windows系统使用IntelliJ IDEA 搭建Hadoop的开发调试环境（一）
查看>>
yum安装lamp
查看>>
Web.Config文件中数据库连接配置
查看>>
[Unity 3D] Unity 3D 性能优化 (一)
查看>>
spring Quartz定时任务调度 时间设置
查看>>
SymmetricDS: 数据库数据同步Database synchronization
查看>>
Disabling OOM killer on Ubuntu 14.04
查看>>
VBS备份脚本
查看>>
CentOS 6.5 自动安装镜像
查看>>