这篇文章主要为大家详细介绍了Kosaraju算法，Kosaraju算法可以计算出一个有向图的强连通分量，具有一定的参考价值，感兴趣的小伙伴们可以参考一下
Kosaraju算法是干什么的？
Kosaraju算法可以计算出一个有向图的强连通分量
什么是强连通分量？
在一个有向图中如果两个结点（结点v与结点w）在同一个环中（等价于v可通过有向路径到达w，w也可以到达v）它们两个就是强连通的，所有互为强连通的点组成了一个集合，在一幅有向图中这种集合的数量就是这幅图的强连通分量的数量
怎么算？？
第一步：计算出有向图 (G) 的反向图 (G反) 的逆后序排列（代码中有介绍）
第二步：在有向图 (G) 中进行标准的深度优先搜索，按照刚才计算出的逆后序排列顺序而非标准顺序
class Kosaraju { private Digraph G; private Digraph reverseG; //反向图 private Stack reversePost; //逆后续排列保存在这 private boolean[] marked; private int[] id; //第v个点在几个强连通分量中 private int count; //强连通分量的数量 public Kosaraju(Digraph G) { int temp; this.G = G; reverseG = G.reverse(); marked = new boolean[G.V()]; id = new int[G.V()]; reversePost = new Stack(); makeReverPost(); //算出逆后续排列 for (int i = 0; i 为什么这样就可以算出强连通分量的数量？（稍微有些费解）
比如有这样一个图，它有五个强连通分量
我们需要证明在26行的dfs(temp)中找到的①全是点temp的强连通点，②且是它全部的强连通点
证明时不要忘了定义：v可通过有向路径到达w，w也可以到达v，则它俩强连通
先证明②：
用反证法，就假如对一个点（点w）深度优先搜索时有一个它的强连通点（点v）没找到。
如果没找到，那就说明 点v 已经在找其他点时标记过了， 但 点v 如果已经被标记过了，因为有一条 v -> w 的有向路径，那 点w 肯定也被找过了，那就不会对 点w 深度优先搜索了。
假设不成立 (*^ω^*)
再证明①：
对一个点（点w）深度优先搜索时找到了一个点（点v），说明有一条 w -> v 的有向路径，再证明有一条 v -> w 的路径就行了，证明有一条 v -> w 的路径，就相当于证明图G的反向图（G反）有一条 w -> v 的有向路径，因为 点w 和 点v 满足那个 逆后序排列，而逆后序排列是在redfs(node)结束时将node加入栈，再从栈中弹出，那说明反向图的深度优先搜索中redfs(v)肯定在redfs(w)前就结束了，那就是两种情况：
■ redfs(v)已经完了redfs(w)才开始
■ redfs(v)是在 redfs(w)开始之后结束之前 结束的，也就是redfs(v)是在redfs(w)内部结束的
第一种情况不可能，因为 G反 有一条 v -> w 的路径（因为G有一条 w -> v 的路径），满足第二中情况即在 G反 中有一条 w -> v 的路径。
终于证完了。
完整代码：
package practice; import java.util.ArrayList; import java.util.Stack; public class TestMain { public static void main(String[] args) { Digraph a = new Digraph(13); a.addEdge(0, 1);a.addEdge(0, 5);a.addEdge(2, 3);a.addEdge(2, 0);a.addEdge(3, 2); a.addEdge(3, 5);a.addEdge(4, 3);a.addEdge(4, 2);a.addEdge(5, 4);a.addEdge(6, 0); a.addEdge(6, 4);a.addEdge(6, 9);a.addEdge(7, 6);a.addEdge(7, 8);a.addEdge(8, 7); a.addEdge(8, 9);a.addEdge(9, 10);a.addEdge(9, 11);a.addEdge(10, 12);a.addEdge(11, 4); a.addEdge(11, 12);a.addEdge(12, 9); Kosaraju b = new Kosaraju(a); System.out.println(b.count()); } } class Kosaraju { private Digraph G; private Digraph reverseG; //反向图 private Stack reversePost; //逆后续排列保存在这 private boolean[] marked; private int[] id; //第v个点在几个强连通分量中 private int count; //强连通分量的数量 public Kosaraju(Digraph G) { int temp; this.G = G; reverseG = G.reverse(); marked = new boolean[G.V()]; id = new int[G.V()]; reversePost = new Stack(); makeReverPost(); //算出逆后续排列 for (int i = 0; i [] node; private int v; public Digraph(int v) { node = (ArrayList[]) new ArrayList[v]; for (int i = 0; i (); this.v = v; } public void addEdge(int v, int w) { node[v].add(w);} public Iterable adj(int v) { return node[v];} public Digraph reverse() { Digraph result = new Digraph(v); for (int i = 0; i 以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持html中文网。
以上就是Kosaraju算法详解的详细内容，更多请关注0133技术站其它相关文章！
