有向图的强连通分支

缘起

图的连通分支的定义是

<S,E> 是图G的子集, 如果S中任何顶点之间可以互相到达的话, 则称S是G的一个连通子集. 如果按照包含偏序关系的极大子集便是连通分支.

分析

对于有向图和无向图而言, 连通分支的含义是不一样的, 因为在有向图中u能到v, 则v一定能到u, 但是有向图中未必.

所以有向图的连通分支又叫做强连通分支, 而无向图的连通分支就叫做连通分支.

无向图的连通分支是容易求的, 只需要遍历即可（不论是bfs还是dfs）.因为无向图u能到v, 则v 一定能到u. 所以只需要遍历而不需要搜索. 就代码细节而言, 就是 isvisited数组不需要改回来. 但是有向图中u 能到v, 反之v不一定能到u. 所以靠遍历是无法求出有向图的强连通分支的（因为遍历只能得到有向图单向的通路，而未必存在反向的通路）.

强连通分支（scc）算法的应用场景例如社交, 有一些人是可以互相连通的. 比如都对某款游戏感兴趣. 这就可以计算出这个圈子，然后集中推销广告（精准营销）

为此，诞生了有向图强连通分支的朴素算法(事后证明就是kosaraju)、tarjan、kosaraju、gabow算法. 后面慢慢讲.