算法-強連通分量和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，如需轉載請自行聯系原作者