简介

该算法主要用于枚举图中每一个强连通分量内的所有顶点。该算法可由以下四部分组成：

对有向图G{\displaystyle G}取逆，得到G{\displaystyle G}的反向图GR{\displaystyle G^{R}}

利用深度优先搜索求出GR{\displaystyle G^{R}}的逆后排序

对G{\displaystyle G}按照上述逆后排序的序列进行深度优先搜索

同一个深度优先搜索递归子程序中访问的所有顶点都在同一个强连通分量内

Java代码实现

publicclassKosarajuAlgorithm{privateboolean[]marked;privateint[]id;privateintcount=-1;privateStackreversePostOrder;publicKosarajuAlgorithm(DigraphG){//G.V()返回有向图G的边数marked=newboolean[G.V()];id=newint[G.V()];//G.reverse()返回的为G的反向图DigraphG_reverse=G.reverse();//本遍循环是将G的反向图的逆后序排列存储在reversePostOrder中for(inti=0;i<G_reverse.V();i++){if(!marked[i]){dfs(G_reverse,i);}}count=0;//按照G的反向图的逆后排序进行深度优先搜索for(inti:reversePostOrder){if(!marked[i]){dfs(G,i);count++;}}}//深度优先搜索publicvoiddfs(DigraphG,intv){marked[v]=true;id[v]=count;for(inti:G.adj(v)){if(!marked[i]){dfs(G,i);}}reversePostOrder.push(v);}}

复杂度

当图是使用邻接表形式组建的，Kosaraju算法需要对整张图进行了两次的完整的访问，每次访问与顶点数V{\displaystyle V}和边数E{\displaystyle E}之和V+E{\displaystyle V+E}成正比，所以可以在线性时间O(V+E){\displaystyle O(V+E)}内访问完成。该算法在实际操作中要比Tarjan算法和基于路径的强连通分量算法（英语：Path-based strong component algorithm）要慢，这两种算法都只需要对图进行一次完整的访问。

当图是使用邻接矩阵形式组建的，算法的时间复杂度为O(V2){\displaystyle O(V^{2})}。

文献及链接

Micha Sharir.A strong connectivity algorithm and its applications to data flow analysis. Computers and Mathematics with Applications 7(1):67–72, 1981]

Kosaraju"s的简要介绍与证明

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。