算法-强连通分量和Kosaraju算法

有向图中，连通性比较好理解，如果两个顶点V和顶点W是可达的，可以称之为强连通的，即存在路径A→B，同时也存在一条有向路径B→A.从之前的有向环的判定过程中其实我们可以得到一个结论就是两个是强连通的当且仅当它们都在一个普通的有向环中。强连通将所有的顶点分为了不同的集合，每个集合都是由相互均为强连通性的顶点的最大子集组成的，我们将这些集合称之为强连通分量。

采用之前有向环中的图片:

API定义:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

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

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

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

<code>@property (assign,nonatomic)  NSInteger count;</code><code>//连通的分量</code>

<code>@property  (strong,nonatomic)  NSMutableArray  *ids;</code><code>//顶点所在的连通分量的标识符</code>

<code>//连通分量递归初始化</code>

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

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

<code>//判断两个顶点之间是否存在连通性</code>

<code>-(BOOL)stronglyConnected:(NSInteger)vertex  otherVertex:(NSInteger)otherVertex;</code>

<code>@end</code>

通过API的定义，如果对比之前之前无向图中的API,我们发现基本上没有变化，具体实现的过程中变化也很小，需要之前基于深度优先搜索的顶点排序，取出逆后序集合进行遍历即可，之后和无向图中一样进行递归判断存储在数组中。

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

<code>@implementation KosarajuCC</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>}</code>

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

<code>}</code>

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

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

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

<code>    </code><code>return</code> <code>_ids;</code>

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

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

<code>    </code><code>if</code> <code>(self) {</code>

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

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

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

<code>        </code><code>}</code>

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

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

<code>        </code><code>for</code> <code>(NSInteger j=0; j&lt;[order.reversePostStack count]; j++) {</code>

<code>            </code><code>NSInteger  temp=[[order.reversePostStack objectAtIndex:j] integerValue];</code>

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

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

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

<code>            </code><code>}</code>

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

<code>//博客园-FlyElephant:http://www.cnblogs.com/xiaofeixiang/</code>

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

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

<code>    </code><code>//同一分量中顶点的赋值</code>

<code>    </code><code>self.ids[vertex]=[NSNumber numberWithInteger:self.count];</code>

<code>    </code><code>for</code> <code>(NSInteger i=0; i&lt;[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 depthSearch: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>-(BOOL)stronglyConnected:(NSInteger)vertex  otherVertex:(NSInteger)otherVertex{</code>

<code>    </code><code>return</code> <code>[self.ids[vertex] integerValue]==[self.ids[otherVertex] integerValue];</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>KosarajuCC  *graphCC=[[KosarajuCC alloc]initWithGraph:graph];</code>

<code>for</code> <code>(NSInteger i=0; i&lt;graphCC.count; i++) {</code>

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

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

<code>        </code><code>if</code> <code>([graphCC.ids[j] integerValue]==i) {</code>

<code>            </code><code>[dataSource addObject:[NSNumber numberWithInteger:j]];</code>

<code>    </code><code>NSLog(</code><code>@"分量%ld:%@"</code><code>,i,[dataSource componentsJoinedByString:</code><code>@"--"</code><code>]);</code>

<code>NSInteger  vertex=0,otherVertex=1;</code>

<code>Boolean  cc=[graphCC stronglyConnected:vertex otherVertex:otherVertex];</code>

<code>NSLog(</code><code>@"节点%ld和节点%ld %@强连通的"</code><code>,vertex,otherVertex,cc==</code><code>true</code><code>?</code><code>@"是"</code><code>:</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>

测试结果:

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