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.

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

- 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.
- Social networks can use SCC to group people that strongly connected by some interests and suggest information for them.
- 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*

- Given directed graph
**G**. - Perform DFS on
**G**to compute finishing times f[u] for all u. - Compute
**G**.^{T} - Perform DFS(
**G**).^{T} - The DFS subtrees common to both
**G**and**G**comprise a SCC.^{T }

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. **L **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