Strongly Connected Graph

A strongly connected graph is a graph such that there is a path connecting each vertex in the graph to another vertex in the graph. The strongly connected components of a directed graph G are the equivalence classes of the relation: u~v <-> path u->v AND path v->u. The ~ relation is an equivalence class, that is, ~ is reflexive, symmetric, and transitive.

Computing the strongly computed components allows you to use the for-free primitives (BFS, DFS, etc) on the components in linear time, which is blazingly fast.

Calling DFS on the right nodes will compute all the SCCs, but on the wrong nodes will just give back the union of multiple SCC's or even the whole graph.

With Kosaraju's Two-Pass Algorithm, we can compute the SCC's in linear time, with just two passes of DFS. Make a new graph with all the edges of original graph reversed. The naive way of implementing this would to run through the graph linearly and construct a new one. An optimization for this would be to just run DFS on the original graph, but going across arcs backwards.

Secondly, run DFS-loop on G^rev. Thirdly, run DFS-loop on G.The first DFS-loop computes the "magic ordering" of the nodes while the second DFS-loop discovers the SCC's one by one.

DFS-loop(graph G)
     global variable t = 0 (for finishing times in first pass, number of nodes finished so far)
     global variable s = null (current source vertex, for leaders in second pass)
     Assume nodes labeled 1 to n
     for i:=n down to 1
          if i not yet explored
               s := i
               DFS(G, i)

DFS(graph G, node i)
     mark i as explored
     set leader(i) := node s
     for each arc(i,j) in G
          if j not yet explored
               DFS(G, j)
     t++
     set f(i) := t [i's finishing time]