算法-有向環和拓撲排序

有向圖中包括有向無環圖和有向有環圖，有向圖在任務排程的時候優先級限制是非常有用的，最常見的是大學的排課系統，比如說計算機作業系統的優先級高于高等數學，我們可以用圖表示為計算機作業系統→高等數學，高等數學高于線性代數，如果這個時候線性代數的優先級高于計算機作業系統，那麼就産生了一個有向環，無法進行排課，課程一般比較多，如果用圖表示去判斷是否存在環路是比較麻煩的一個事情，是以通常需要判斷有向圖中是否含有向環。

如果有向圖中的某個節點可以按照路徑的方向從某個節點開始并傳回本身，形成了閉環可以判定是圖中含有有向環。有向環中的判定和之前的無向圖中的深度搜尋類似，如果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哈希