图是由顶点和边连接而成，如果边是没有方向的是就是之前文章中说的无向图，关于无向图可以参考本人之前的文章，如果边是有方向的，则称之为有向图。从顶点A→B，我们可以理解为A到B可达，有向图和无向图一样通过邻接表保存每一条边，由于边是有方向的，因此在添加边的过程中只需要添加一条边即可。关于可达性一个节点数组的可达性，采用的方法是之前的深度优先搜索一样的代码，通过递归将标记位Bool标记位判断数组中每个顶点的可达性。为了测试，选择下面一张有向图:

有向图基础

通过图片我们可以发现图中有13个节点，22条边，顶点0指出的节点有1，5，指入的节点有2，6，我们先实现所有顶点指出的节点，之后可以通过反转判断所有节点的指入节点：

@interface Digraph : NSObject//顶点的总数@property  (assign,nonatomic) NSInteger  vertexs;//边的数总数@property (assign,nonatomic) NSInteger  edges;//连接点的边@property (strong,nonatomic)  NSMutableArray  *adjDataSource;-(instancetype)initWithVertex:(NSInteger)vertexs;//添加一条有向边 startVertex→endVertex-(void)addEdges:(NSInteger)startVertex  endVertex:(NSInteger)endVertex;-(Digraph *)reverse;//该图的反向图@end

实现代码:

@implementation Digraph-(instancetype)initWithVertex:(NSInteger)vertexs{    self=[super init];    if (self) {        self.vertexs=vertexs;        for (NSInteger i=0; i

测试代码:

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];        for (NSInteger i=0; i<[graph.adjDataSource count]; i++) {            NSLog(@"节点%ld指出→的节点:%@",i,[graph.adjDataSource[i] componentsJoinedByString:@"--"]);        }        NSLog(@"技术交流群:%@",@"228407086");        NSLog(@"原文地址:http://www.cnblogs.com/xiaofeixiang");

测试效果:

现在可以判断出顶点的指出节点，实现文件中有一个reverse方法将图反转，求出顶点的转入节点:

Digraph  *digraph=[graph reverse];        for (NSInteger i=0; i<[digraph.adjDataSource count]; i++) {            NSLog(@"指入%ld⬅️的节点:%@",i,[digraph.adjDataSource[i] componentsJoinedByString:@"--"]);        }        NSLog(@"技术交流群:%@",@"228407086");        NSLog(@"原文地址:http://www.cnblogs.com/xiaofeixiang");

测试效果:

可达性

可达性的判断和之前的深度优先搜索基本没变化，先来看一下需要实现的方法:

@interface DirectedDFS : NSObject//标记数组@property  (strong,nonatomic)  NSMutableArray  *marked;//找到arr中顶点可达的所有顶点-(instancetype)initDirectedDFSWithVertex:(Digraph *)graph  vertexArr:(NSArray *)arr;//在graph中找到从vertex可达的所有顶点-(void)directedDFS:(Digraph *)graph  vertex:(NSInteger)vertex;//vertex是否可达-(Boolean)isMarked:(NSInteger)vertex;@end

实现代码:

@implementation DirectedDFS#pragma mark  getter and setter-(NSMutableArray *)marked{    if (!_marked) {        _marked=[[NSMutableArray alloc]initWithCapacity:1];    }    return _marked;}-(instancetype)initDirectedDFSWithVertex:(Digraph *)graph vertexArr:(NSArray *)arr{    self=[super init];    if (self) {        for (NSInteger i=0; i

测试代码:

NSArray  *sources=[NSArray arrayWithObjects:@"2", nil];        DirectedDFS  *directedDFS=[[DirectedDFS alloc]initDirectedDFSWithVertex:graph vertexArr:sources];        NSMutableArray  *reachableArr=[[NSMutableArray alloc]initWithCapacity:1];        for (NSInteger i=0; i

测试效果: