算法-有向圖及可達性

圖是由頂點和邊連接配接而成，如果邊是沒有方向的是就是之前文章中說的無向圖，關于無向圖可以參考本人之前的文章，如果邊是有方向的，則稱之為有向圖。從頂點A→B，我們可以了解為A到B可達，有向圖和無向圖一樣通過鄰接表儲存每一條邊，由于邊是有方向的，是以在添加邊的過程中隻需要添加一條邊即可。關于可達性一個節點數組的可達性，采用的方法是之前的深度優先搜尋一樣的代碼，通過遞歸将标記位Bool标記位判斷數組中每個頂點的可達性。為了測試，選擇下面一張有向圖:

通過圖檔我們可以發現圖中有13個節點，22條邊，頂點0指出的節點有1，5，指入的節點有2，6，我們先實作所有頂點指出的節點，之後可以通過反轉判斷所有節點的指入節點：

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

<code>//頂點的總數</code>

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

<code>//邊的數總數</code>

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

<code>//連接配接點的邊</code>

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

<code>-(instancetype)initWithVertex:(NSInteger)vertexs;</code>

<code>//添加一條有向邊 startVertex→endVertex</code>

<code>-(</code><code>void</code><code>)addEdges:(NSInteger)startVertex endVertex:(NSInteger)endVertex;</code>

<code>-(Digraph *)reverse;</code><code>//該圖的反向圖</code>

實作代碼:

<code>@implementation Digraph</code>

<code>-(instancetype)initWithVertex:(NSInteger)vertexs{</code>

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

<code> </code><code>self.vertexs=vertexs;</code>

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

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

<code> </code><code>[self.adjDataSource addObject:neighbourVertex];</code><code>//建立鄰接表,将所有連結清單初始化為空</code>

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

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

<code>-(</code><code>void</code><code>)addEdges:(NSInteger)startVertex endVertex:(NSInteger)endVertex{</code>

<code> </code><code>//将endVertex添加到startVertex的連結清單中</code>

<code> </code><code>[self.adjDataSource[startVertex] insertObject:[NSNumber numberWithInteger:endVertex] atIndex:0];</code>

<code> </code><code>self.edges=self.edges+1;</code>

<code>-(Digraph *)reverse{ </code>

<code> </code><code>Digraph *digraph=[[Digraph alloc]initWithVertex:self.vertexs];</code>

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

<code> </code><code>NSMutableArray *tempArr=self.adjDataSource[i];</code>

<code> </code><code>for</code> <code>(NSInteger j=0; j<[tempArr count]; j++) {</code>

<code> </code><code>[digraph addEdges:[tempArr[j] integerValue] endVertex:i];</code>

<code> </code><code>return</code> <code>digraph;</code>

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

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

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

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

<code> </code><code>return</code> <code>_adjDataSource;</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>for</code> <code>(NSInteger i=0; i<[graph.adjDataSource count]; i++) {</code>

<code> </code><code>NSLog(</code><code>@"節點%ld指出→的節點:%@"</code><code>,i,[graph.adjDataSource[i] componentsJoinedByString:</code><code>@"--"</code><code>]);</code>

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

<code>NSLog(</code><code>@"原文位址:http://www.cnblogs.com/xiaofeixiang"</code><code>);</code>

測試效果:

現在可以判斷出頂點的指出節點，實作檔案中有一個reverse方法将圖反轉，求出頂點的轉入節點:

<code>Digraph *digraph=[graph reverse];</code>

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

<code> </code><code>NSLog(</code><code>@"指入%ld⬅️的節點:%@"</code><code>,i,[digraph.adjDataSource[i] componentsJoinedByString:</code><code>@"--"</code><code>]);</code>

可達性的判斷和之前的深度優先搜尋基本沒變化，先來看一下需要實作的方法:

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

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

<code>//找到arr中頂點可達的所有頂點</code>

<code>-(instancetype)initDirectedDFSWithVertex:(Digraph *)graph vertexArr:(NSArray *)arr;</code>

<code>//在graph中找到從vertex可達的所有頂點</code>

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

<code>//vertex是否可達</code>

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

<code>@implementation DirectedDFS</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>-(instancetype)initDirectedDFSWithVertex:(Digraph *)graph vertexArr:(NSArray *)arr{</code>

<code> </code><code>for</code> <code>(NSInteger i=0; i<graph.vertexs;i++) {</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 j=0; j<[arr count]; j++) {</code>

<code> </code><code>if</code> <code>(![self isMarked:[arr[j] integerValue]]) {</code>

<code> </code><code>[self directedDFS:graph vertex:[arr[j] integerValue]];</code>

<code>//部落格園-FlyElephant:http://www.cnblogs.com/xiaofeixiang/</code>

<code>-(</code><code>void</code><code>)directedDFS:(Digraph *)graph vertex:(NSInteger)vertex{</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 isMarked:temp]) {</code>

<code> </code><code>[self directedDFS:graph vertex:temp];</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>NSArray *sources=[NSArray arrayWithObjects:</code><code>@"2"</code><code>, nil];</code>

<code>DirectedDFS *directedDFS=[[DirectedDFS alloc]initDirectedDFSWithVertex:graph vertexArr:sources];</code>

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

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

<code> </code><code>if</code> <code>(directedDFS.marked[i]&&directedDFS.marked[i]!=[NSNull </code><code>null</code><code>]) {</code>

<code> </code><code>[reachableArr addObject:[NSNumber numberWithInteger:i]];</code>

<code>NSLog(</code><code>@"可達的節點:%@"</code><code>,[reachableArr componentsJoinedByString:</code><code>@"--"</code><code>]);</code>

<code>NSLog(</code><code>@"部落格園-FlyElephant:http://www.cnblogs.com/xiaofeixiang"</code><code>);</code>

本文轉自Fly_Elephant部落格園部落格，原文連結：http://www.cnblogs.com/xiaofeixiang/p/4703980.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哈希