算法-有向图及可达性

图是由顶点和边连接而成，如果边是没有方向的是就是之前文章中说的无向图，关于无向图可以参考本人之前的文章，如果边是有方向的，则称之为有向图。从顶点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哈希