Kosaraju算法详解

Kosaraju算法详解算法详解

主要为大家详细介绍了Kosaraju算法，Kosaraju算法可以计算出一个有向图的强连通分量，具有一定的参考价

值，感兴趣的小伙伴们可以参考一下

Kosaraju算法是干什么的？算法是干什么的？

Kosaraju算法可以计算出一个有向图的强连通分量

什么是强连通分量？什么是强连通分量？

在一个有向图中如果两个结点（结点v与结点w）在同一个环中（等价于同一个环中（等价于v可通过有向路径到达可通过有向路径到达w，，w也可以到达也可以到达v））它们两个就

是强连通的，所有互为强连通的点组成了一个集合集合，在一幅有向图中这种集合的数量数量就是这幅图的强连通分量的数量

private Stack<Integer> 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()];

}

for (int i = 0; i < G.V(); i++) { //算出强连通分量

temp = reversePost.pop();

if (!marked[temp]) {

count++;

dfs(temp);

}

}

}

redfs(i);

}

}

private void redfs(int v) {

marked[v] = true;

for (Integer w: reverseG.adj(v)) { //adj(v)返回的是v指向的结点的集合

if (!marked[w])

redfs(w);

}

marked[v] = true;

id[v] = count;

for (Integer w: G.adj(v)) {

if (!marked[w])

dfs(w);

}