The Kosaraju algorithm can be used that if the underlying store is an AdjacencyList can be blazing fast with O (V+E) time.
Implemented as per wiki:
Kosaraju
- Let G be a directed graph and S be an empty stack.
- While S does not contain all vertices:
- Choose an arbitrary vertex v not in S. Perform a depth-first search starting at v. Each time that depth-first search finishes expanding a vertex u, push u onto S.
- Reverse the directions of all arcs to obtain the transpose graph.
- While S is nonempty:
- Pop the top vertex v from S. Perform a depth-first search starting at v in the transpose graph. The set of visited vertices will give the strongly connected component containing v; record this and remove all these vertices from the graph G and the stack S. Equivalently, breadth-first search (BFS) can be used instead of depth-first search.
Source Code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
public class Kosaraju { Graph g; Graph gRev; private Stack finishingTime = new Stack(); private Set discoveredNodes = new HashSet(); private List listOfStronglyConnectedNodes = new ArrayList(); /** * Step 1 from description above */ public void gatherFinishingTime() { for (int i : g.getVertices()) { if (!discoveredNodes.contains(i)) { DFSLoop1(g, i); } } } public void DFSLoop1(Graph gArg, int startingNode) { discoveredNodes.add(startingNode); for (int edge : gArg.getEdges(startingNode)) { if (!discoveredNodes.contains(edge)) { DFSLoop1(gArg, edge); } } finishingTime.push(startingNode); } /** * Step 2 from description above: * * Precondition: gRev is available. * */ public void gatherStronglyConnected() { discoveredNodes.clear(); while (!finishingTime.isEmpty()) { int v = finishingTime.pop(); if (discoveredNodes.contains(v)) { continue; } listOfStronglyConnectedNodes.clear(); DFSLoop2(gRev, v); // this will print the list of the strongly conn comp. PrintUtil.printList(listOfStronglyConnectedNodes); } } public void DFSLoop2(Graph gArg, int startingNode) { discoveredNodes.add(startingNode); listOfStronglyConnectedNodes.add(startingNode); for (int edge : gArg.getEdges(startingNode)) { if (!discoveredNodes.contains(edge)) { DFSLoop2(gArg, edge); } } } /** * Disregard m for now. Create a static graph * */ public Graph createGraph(int m) { Graph g = new Graph(9); g.addEdge(1, 4); g.addEdge(2, 8); g.addEdge(3, 6); g.addEdge(4, 7); g.addEdge(5, 2); g.addEdge(6, 0); g.addEdge(7, 1); g.addEdge(8, 6); g.addEdge(8, 5); g.addEdge(0, 7); g.addEdge(0, 3); return g; } public static void main(String[] args) { Kosaraju k = new Kosaraju(); k.g = k.createGraph(5); k.gRev = k.g.reverseGraph(); k.gatherFinishingTime(); k.gatherStronglyConnected(); } } |
