SCC Computing the strongly connected components

A strongly connected component is a set of vertices and edges so that every pair of vertices in the set can get to each other through some edges in the set.

Given directed graph G = (V, E), finding all of the strongly connected components.

Gr = (V, Er), where Er is the set of edges in which every edge are the reverse version of the corresponding edge in E.

leader[] is an array that leader[i] is the leader of the strongly connected components which ith vertex belongs to.

The algorithm:

• global variable s = NULL; stack finish_order;
• for every vertex v:
  • if v was explored, continue;
  • DFS(Gr, v)
• while (!finish_order.isEmpty())
  • v = finish_order.pop();
  • if v was explored, continue;
  • s = v;
  • DFS(G, v)

DFS(G, v):

• mark v as explored;
• set leader[v] = s;
• for each edge e(v, w) of v:
  • if w was explored, continue;
  • DFS(G, w)
• finish_order.push(v);

• The directed graph can be seen as a “meta-graph”, which means that we can see each strongly connected component as a single vertex. If there are several SCCs (# > 1) and the original graph is connected, the “meta-graph” is acyclic.

• The finishing order of a DFS-Loop:

  In every strongly connected component, there is at least one node finishing after all of the nodes in the component which is “after” the current component shown in the “meta-graph”

• The above property guarantees that in the second DFS_Loop, we can always begin our traversal in the “front” SCC.