看论文的时候,看到Kosaraju算法。Kosaraju是一个强连通分图的发现算法,如有代码中有详细的注释,所以就不赘述了。直接上码(使用webgraph库实现,在我之前的文章中,对webgraph有相关的介绍):
package cn.edu.dlut.wisdom;
import it.unimi.dsi.fastutil.ints.*;
import it.unimi.dsi.fastutil.objects.*;
import it.unimi.dsi.webgraph.*;
import java.util.Comparator;
/**
* @author You Wang* Kosaraju算法,用来发现强连通分量* 算法过程如下:* G:有向图;S:空栈* while S中不包含G中所有顶点* 任选一个不在S中的节点v* 从v开始进行深度优先搜素,每次将访问到的节点u压入S中* 反转G中所有的边* while S非空* 从S中弹出结点v* 从v开始进行深度优先搜索,所有访问到的结点构成强连通分图,记录下来* 从G和S中删除这些结点*/public class Kosaraju {private ImmutableGraph graph;
private ImmutableGraph igraph;
private ImmutableGraph workGraph;
private ObjectAVLTreeSet<IntAVLTreeSet> sccs;
private IntArrayList stack;
private boolean[] visited;private int numNodes;public Kosaraju(ImmutableGraph graph) {
this.graph = graph;
igraph = Transform.transpose(graph);numNodes = graph.numNodes();}public Kosaraju(ImmutableGraph graph, ImmutableGraph igraph) {
this.graph = graph;
this.igraph = igraph;
numNodes = graph.numNodes();}public ObjectAVLTreeSet<IntAVLTreeSet> compute() {
stack = new IntArrayList();
visited = new boolean[numNodes];workGraph = graph;// dfs the graph, adding nodes to the stack
for(int i = 0; i < numNodes; i++)if(!stack.contains(i))
dfs(i, true);
workGraph = igraph;Comparator cmp = new Comparator() {
public int compare(Object o1, Object o2) {if(o1 instanceof IntAVLTreeSet && o2 instanceof IntAVLTreeSet) {IntAVLTreeSet s1 = (IntAVLTreeSet)o1;IntAVLTreeSet s2 = (IntAVLTreeSet)o2;if (s1.size() != s2.size())
return s1.size() - s2.size();
else
{int[] a1 = s1.toIntArray();
int[] a2 = s2.toIntArray();
for (int i = 0; i < a1.length; i++)if (a1[i] != a2[i])
return a1[i] - a2[i];
return 0;
}}else
throw new IllegalArgumentException("The argument must be an IntAVLTreeSet");}};sccs = new ObjectAVLTreeSet<IntAVLTreeSet>(cmp);
while(!stack.isEmpty()) {
IntAVLTreeSet component = new IntAVLTreeSet();
int v = stack.popInt();
component.add(v);dfs(v, false);
// any components we visited are strongly connected
// remove them from the starck and add them to the component
IntIterator it = stack.iterator();while(it.hasNext()) {
int n = it.nextInt();
if(!visited[n]) {
component.add(n);it.remove();}}if(component.size() != 0)
sccs.add(component);}return sccs;
}private void dfs(int node, boolean forward) {visited[node] = forward;if(workGraph.outdegree(node) == 0) {
if(forward)
stack.push(node);return;
}for(int n : workGraph.successorArray(node))if(visited[n] != forward)
dfs(n, forward);if(forward)
stack.push(node);}}
其中的set排序,个人感觉不尽完美,不知道各位有何高见,欢迎指正。