Strongly Connected Components

Another useful application of the depth-first search algorithm, is decomposing of the directed graph into the strongly connected components or SCC. A strongly connected component of the graph is a maximal set of vertices in which there is a path from any vertex to any other vertex in both directions.

scc4

The above directed graph has three strongly connected components. Because, component #1 has vertices {A, E, F} and from each of these vertices you can get to the another. The same for component #2 and #3.

Application
  1. When all strongly connected components are defined we can easily check whether two vertices are strongly connected. Just test these vertices are in the same component.
  2. Social networks can use SCC to group people that strongly connected by some interests and suggest information for them.
  3. SCC helps to reduce complex graphs into relevant nodes, thus analysis of the graph will be much easier.

Implementation

There are several common approaches that can decompose graph into SCC in linear time. One of them is Kosaraju’s algorithm which requires two passes of depth-first search to make a decomposition.

Kosaraju’s algorithm KA

  1. Given directed graph G.
  2. Perform DFS on G to compute finishing times f[u] for all u.
  3. Compute GT.
  4. Perform DFS(GT).
  5. The DFS subtrees common to both G and GT comprise a SCC.

Another approach was proposed by american mathematician Robert Tarjan and it’s also based on depth-first search algorithm. The vertices are indexed as they are traversed by DFS. While returning from the recursion of DFS, every vertex V gets assigned a vertex L as a representative. is a vertex with the least index that can be reach from V. Nodes with the same representative assigned are located in the same strongly connected component.

Here goes my Java implementations of Tarjan’s and Kosaraju’s algorithms on GitHub: todo: https://github.com/alexvolov/algorithms-and-data-structures/blob/master/src/main/java/com/alexvolov/ads/algorithms/graph/StronglyConnectedComponents.java

Leave a Reply