算法-有向环和拓扑排序

有向图中包括有向无环图和有向有环图，有向图在任务调度的时候优先级限制是非常有用的，最常见的是大学的排课系统，比如说计算机操作系统的优先级高于高等数学，我们可以用图表示为计算机操作系统→高等数学，高等数学高于线性代数，如果这个时候线性代数的优先级高于计算机操作系统，那么就产生了一个有向环，无法进行排课，课程一般比较多，如果用图表示去判断是否存在环路是比较麻烦的一个事情，所以通常需要判断有向图中是否含有向环。

如果有向图中的某个节点可以按照路径的方向从某个节点开始并返回本身，形成了闭环可以判定是图中含有有向环。有向环中的判定和之前的无向图中的深度搜索类似，如果A→B，在之前图的辅助数据结构我们存储的是所以为A对应的值中含有B，如果索引B中含有值A，即含有有向环。

有向环检测的API跟之前的深度搜索多了一个保存有向环的中节点的数组，和递归需要调用的数组:

<code>@</code><code>interface</code> <code>DirectedCycle : NSObject</code>

<code>@property (strong,nonatomic) NSMutableArray *marked;</code>

<code>@property (strong,nonatomic) NSMutableArray *cycle;</code><code>//有向环中的所有顶点(存在有向环的情况)</code>

<code>@property (strong,nonatomic) NSMutableArray *onStack;</code><code>//递归调用的栈上的所有顶点</code>

<code>//从起点到一个顶点的已知路径上的最后一个顶点</code>

<code>@property (strong,nonatomic) NSMutableArray *edgeTo;</code>

<code>@property (assign,nonatomic) Boolean hasCycle;</code>

<code>-(instancetype)initWithGraph:(Digraph *)graph;</code>

<code>-(</code><code>void</code><code>)depthSearch:(Digraph *)graph vertex:(NSInteger)vertex;</code>

实现代码:

<code>@implementation DirectedCycle</code>

<code>#pragma mark getter and setter</code>

<code>-(NSMutableArray *)marked{</code>

<code> </code><code>if</code> <code>(!_marked) {</code>

<code> </code><code>_marked=[[NSMutableArray alloc]initWithCapacity:1];</code>

<code> </code><code>return</code> <code>_marked;</code>

<code>-(NSMutableArray *)onStack{</code>

<code> </code><code>if</code> <code>(!_onStack) {</code>

<code> </code><code>_onStack=[[NSMutableArray alloc]initWithCapacity:1];</code>

<code> </code><code>return</code> <code>_onStack;</code>

<code>-(NSMutableArray *)edgeTo{</code>

<code> </code><code>if</code> <code>(!_edgeTo) {</code>

<code> </code><code>_edgeTo=[[NSMutableArray alloc]initWithCapacity:1];</code>

<code> </code><code>return</code> <code>_edgeTo;</code>

<code>-(instancetype)initWithGraph:(Digraph *)graph{</code>

<code> </code><code>self=[super init];</code>

<code> </code><code>for</code> <code>(NSInteger i=0; i<graph.vertexs;i++) {</code>

<code> </code><code>[self.onStack addObject:[NSNull </code><code>null</code><code>]];</code>

<code> </code><code>[self.edgeTo addObject:[NSNull </code><code>null</code><code>]];</code>

<code> </code><code>[self.marked addObject:[NSNull </code><code>null</code><code>]];</code>

<code> </code><code>//遍历图的顶点</code>

<code> </code><code>for</code> <code>(NSInteger s=0; s<graph.vertexs; s++) {</code>

<code> </code><code>if</code> <code>(![self isMarked:s]) {</code>

<code> </code><code>[self depthSearch:graph vertex:s];</code>

<code> </code><code>return</code> <code>self;</code>

<code>//http://www.cnblogs.com/xiaofeixiang/</code>

<code>-(</code><code>void</code><code>)depthSearch:(Digraph *)graph vertex:(NSInteger)vertex{</code>

<code> </code><code>self.onStack[vertex]=[NSNumber numberWithBool:</code><code>true</code><code>];</code>

<code> </code><code>self.marked[vertex]=[NSNumber numberWithBool:</code><code>true</code><code>];</code>

<code> </code><code>for</code> <code>(NSInteger i=0; i<[graph.adjDataSource[vertex] count]; i++) {</code>

<code> </code><code>NSInteger temp=[[graph.adjDataSource[vertex] objectAtIndex:i] integerValue];</code>

<code> </code><code>if</code> <code>([self hasCycle]) </code><code>return</code><code>;</code>

<code> </code><code>else</code> <code>if</code> <code>(![self isMarked:temp]) {</code>

<code> </code><code>self.edgeTo[temp]=[NSNumber numberWithInteger:vertex];</code>

<code> </code><code>[self depthSearch:graph vertex:temp];</code>

<code> </code><code>}</code><code>else</code> <code>if</code><code>([self isStack:temp]){</code>

<code> </code><code>self.cycle=[[NSMutableArray alloc]initWithCapacity:1];</code>

<code> </code><code>for</code> <code>(NSInteger i=vertex; i!=temp; i=[self.edgeTo[i] integerValue]) {</code>

<code> </code><code>[self.cycle insertObject:[NSNumber numberWithInteger:i] atIndex:0];</code>

<code> </code><code>[self.cycle insertObject:[NSNumber numberWithInteger:temp] atIndex:0];</code>

<code> </code><code>[self.cycle insertObject:[NSNumber numberWithInteger:vertex] atIndex:0];</code>

<code> </code><code>self.onStack[vertex]=[NSNumber numberWithBool:</code><code>false</code><code>];</code>

<code>-(Boolean)hasCycle{</code>

<code> </code><code>return</code> <code>[self.cycle count]>0;</code>

<code>-(Boolean)isMarked:(NSInteger)vertex{</code>

<code> </code><code>return</code> <code>self.marked[vertex]==[NSNull </code><code>null</code><code>]?</code><code>false</code><code>:[self.marked[vertex] boolValue];</code>

<code>-(Boolean)isStack:(NSInteger)vertex{</code>

<code> </code><code>return</code> <code>self.onStack[vertex]==[NSNull </code><code>null</code><code>]?</code><code>false</code><code>:[self.onStack[vertex] boolValue];</code>

测试代码:

<code>Digraph *graph=[[Digraph alloc]initWithVertex:13];</code>

<code>[graph addEdges:4 endVertex:2];</code>

<code>[graph addEdges:2 endVertex:3];</code>

<code>[graph addEdges:3 endVertex:2];</code>

<code>[graph addEdges:6 endVertex:0];</code>

<code>[graph addEdges:0 endVertex:1];</code>

<code>[graph addEdges:2 endVertex:0];</code>

<code>[graph addEdges:11 endVertex:12];</code>

<code>[graph addEdges:12 endVertex:9];</code>

<code>[graph addEdges:9 endVertex:10];</code>

<code>[graph addEdges:9 endVertex:11];</code>

<code>[graph addEdges:8 endVertex:9];</code>

<code>[graph addEdges:10 endVertex:12];</code>

<code>[graph addEdges:11 endVertex:4];</code>

<code>[graph addEdges:4 endVertex:3];</code>

<code>[graph addEdges:3 endVertex:5];</code>

<code>[graph addEdges:7 endVertex:8];</code>

<code>[graph addEdges:8 endVertex:7];</code>

<code>[graph addEdges:5 endVertex:4];</code>

<code>[graph addEdges:0 endVertex:5];</code>

<code>[graph addEdges:6 endVertex:4];</code>

<code>[graph addEdges:6 endVertex:9];</code>

<code>[graph addEdges:7 endVertex:6];</code>

<code>DirectedCycle *directedCycle=[[DirectedCycle alloc]initWithGraph:graph];</code>

<code>if</code> <code>([directedCycle.cycle count]) {</code>

<code> </code><code>NSLog(</code><code>@"形成有向环的节点为:%@"</code><code>,[directedCycle.cycle componentsJoinedByString:</code><code>@"--"</code><code>]);</code>

<code>NSLog(</code><code>@"技术交流群:%@"</code><code>,</code><code>@"228407086"</code><code>);</code>

<code>NSLog(</code><code>@"博客园-FlyElephant:http://www.cnblogs.com/xiaofeixiang"</code><code>);</code>

测试效果:

拓扑排序能解决我们最开始所说的排课问题，任务调度问题，不过只能对有向无环图(Directed Acyclic Graph简称DAG)进行排序，上面的有向环检测可以作为拓扑排序的一个辅助。拓扑排序在同样可以在深度优先搜索上面进行修改，深度搜索会访问每个顶点刚好一次，可以在深度搜索递归的时候将参数顶点存放在一个数据结构中，遍历数据结构就可以访问图中所有的顶点，遍历的书序取决于调用的的时间，可以在递归之前也可以在递归之后。

通常来说有三种排列顺序:

前序:在递归之前加入数组中；

后序:在递归之后加入数组中；

逆后序:在递归值周加入数组中，不过每次都存放在首位，类似栈;

顶点排序:

<code>@</code><code>interface</code> <code>DepthFirstOrder : NSObject</code>

<code>//记录顶点是否被标记</code>

<code>@property (strong,nonatomic) NSMutableArray *preQueue;</code><code>//所有顶点的前序排列</code>

<code>@property (strong,nonatomic) NSMutableArray *postQueue;</code><code>//所有顶点的后序排列</code>

<code>@property (strong,nonatomic) NSMutableArray *reversePostStack;</code><code>//所有顶点的逆后序排列</code>

<code>@property (assign,nonatomic) NSInteger count;</code>

<code>//找到与七点vertex所有连通的节点</code>

<code>//节点是否被标记</code>

<code>-(Boolean)isMarked:(NSInteger)vertex;</code>

实现文件:

<code>@implementation DepthFirstOrder</code>

<code>-(NSMutableArray *)preQueue{</code>

<code> </code><code>if</code> <code>(!_preQueue) {</code>

<code> </code><code>_preQueue=[[NSMutableArray alloc]initWithCapacity:1];</code>

<code> </code><code>return</code> <code>_preQueue;</code>

<code>-(NSMutableArray *)postQueue{</code>

<code> </code><code>if</code> <code>(!_postQueue) {</code>

<code> </code><code>_postQueue=[[NSMutableArray alloc]initWithCapacity:1];</code>

<code> </code><code>return</code> <code>_postQueue;</code>

<code>-(NSMutableArray *)reversePostStack{</code>

<code> </code><code>if</code> <code>(!_reversePostStack) {</code>

<code> </code><code>_reversePostStack=[[NSMutableArray alloc]initWithCapacity:1];</code>

<code> </code><code>return</code> <code>_reversePostStack;</code>

<code> </code><code>[self.preQueue addObject:[NSNumber numberWithInteger:vertex]];</code>

<code> </code><code>self.count++;</code>

<code> </code><code>if</code> <code>(![self isMarked:temp]) {</code>

<code> </code><code>[self.postQueue addObject:[NSNumber numberWithInteger:vertex]];</code>

<code> </code><code>[self.reversePostStack insertObject:[NSNumber numberWithInteger:vertex] atIndex:0];</code>

有向环检查和顶点排序都是为拓扑排序准备的，拓扑排序只需要调用即可:

<code>@</code><code>interface</code> <code>TopologicalSort : NSObject</code>

<code>@property (strong,nonatomic) NSMutableArray *order;</code>

<code>-(instancetype)initWithDigraph:(Digraph *)graph;</code>

<code>@implementation TopologicalSort</code>

<code>#pragma mark getter and setter</code>

<code>-(NSMutableArray *)order{</code>

<code> </code><code>if</code> <code>(!_order) {</code>

<code> </code><code>_order=[[NSMutableArray alloc]initWithCapacity:1];</code>

<code> </code><code>return</code> <code>_order;</code>

<code>-(instancetype)initWithDigraph:(Digraph *)graph{</code>

<code> </code><code>DirectedCycle *cyclefinder=[[DirectedCycle alloc]initWithGraph:graph];</code>

<code> </code><code>if</code> <code>(!cyclefinder.hasCycle) {</code>

<code> </code><code>DepthFirstOrder *dfs=[[DepthFirstOrder alloc]initWithGraph:graph];</code>

<code> </code><code>self.order=dfs.reversePostStack;</code>

我们可以通过下面这幅图检测一下程序的正确性:

<code>Digraph *digraph=[[Digraph alloc]initWithVertex:13];</code>

<code>[digraph addEdges:0 endVertex:6];</code>

<code>[digraph addEdges:0 endVertex:1];</code>

<code>[digraph addEdges:0 endVertex:5];</code>

<code>[digraph addEdges:2 endVertex:0];</code>

<code>[digraph addEdges:2 endVertex:3];</code>

<code>[digraph addEdges:3 endVertex:5];</code>

<code>[digraph addEdges:5 endVertex:4];</code>

<code>[digraph addEdges:6 endVertex:4];</code>

<code>[digraph addEdges:6 endVertex:9];</code>

<code>[digraph addEdges:7 endVertex:6];</code>

<code>[digraph addEdges:8 endVertex:7];</code>

<code>[digraph addEdges:9 endVertex:10];</code>

<code>[digraph addEdges:9 endVertex:12];</code>

<code>[digraph addEdges:9 endVertex:11];</code>

<code>[digraph addEdges:11 endVertex:12];</code>

<code>TopologicalSort *logicSort=[[TopologicalSort alloc]initWithDigraph:digraph];</code>

<code>for</code> <code>(NSInteger i=0; i<[logicSort.order count]; i++) {</code>

<code> </code><code>NSLog(</code><code>@"节点%ld"</code><code>,[logicSort.order[i] integerValue]);</code>

测试结果:

如果用节点表示可能会更直接一点，效果如下:

本文转自Fly_Elephant博客园博客，原文链接：http://www.cnblogs.com/xiaofeixiang/p/4713701.html，如需转载请自行联系原作者

算法-有向环和拓扑排序

继续阅读

Codeforces 1417 D. Make Them Equal(思维+构造)

查找算法之二分查找查找算法之二分查找

查找算法学习之二分查找（Python版本）——BinarySearch

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

Command Network(POJ 3164)---定根最小树形图模板题题目描述输入格式输出格式输入样例输出样例分析源程序

开源低带宽语音编解码器

241 Different Ways to Add Parentheses（C代码版）

【趋高机器视觉】机器视觉技术原理解析及解决方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制规程及特点4． CSMA/CD协议5． CSMA/CD的优点6．结束语

极大似然法(ML)与最大期望法(EM)

C++ 第十五周报告1--《冒泡法排序》

笔试面试题目：滑动窗口(二)

数据结构与算法（27）——排序（二）

Dijkstra--简易版（最短路径）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

hdu7108哈希