Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm
Tags: computerscience, algorithms, datastructures, csharp
Published: 2020-03-09 03:51:58

If you are unfamiliar with graphs, check out some of my earlier posts on them.

## Resources:

1. [Video explanation](https://www.youtube.com/watch?v=TyWtx7q2D7Y)
1. [Article explanation](https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm)
1. [Implementation](https://github.com/williamfiset/Algorithms/blob/master/src/main/java/com/williamfiset/algorithms/graphtheory/TarjanSccSolverAdjacencyList.java)

Takeaways:

![Strongly Connected Components](https://dev-to-uploads.s3.amazonaws.com/i/e8d54d3ffyhms5as94o8.jpg)

* A **strongly connected component** in a directed graph is a partition or sub-graph where each vertex of the component is reachable from every other vertex in the component. 
* Strongly connected components are always the _maximal_ sub-graph, meaning none of their vertices are part of another strongly connected component.
* Finding strongly connected components is very similar to finding articulation points & bridges. Many of the solutions for finding them involve **depth-first search** (DFS).
* One way to find strongly connected components is using **Tarjan's Algorithm**.
* Tarjan's Algorithm uses DFS and a stack to find strongly connected components.
* The algorithm overview is:
   * For every unvisited vertex `v` in the graph, perform DFS.
   * At the start of each DFS routine, mark the current vertex `v` as visited, push `v` onto the stack, and assign `v` an ID and low-link value.
   * Initially, like with articulation points & bridges, the ID and low-link values of `v` will be the same. 
   * Increment the integer value we are using as the ID/low-link seed. So the next vertex `w` to enter our DFS routine will get a higher value for both (compared to `v`).
   * For every adjacent vertex `u` of `v`, if `u` is unvisited, perform DFS (recursive call).
   * On exit of the recursive DFS call, or if `u` had already been visited, check if `u` is on the stack.
   * If `u` is on the stack, update the low-link value of `v` to be smallest between `low-link[v]` and `low-link[u]`
      * low-link represents the _earliest_ ancestor of a vertex (a lower value means the vertex entered DFS earlier). In other words, low-link is the ID of the earliest vertex `y` vertex `v` is connected to.
   * After exploring all adjacent vertices of `v` check if the ID of `v` is the same as it's low-link value
   * If they are the same, then `v` is the root of a strongly connected component.
   * If they are the same, pop all vertices off the stack up to and including `v`. All of these vertices represent a single strongly connected component
  * Complete the above steps for the entire graph, and all strongly connected components will be discovered.
* Time complexity of Tarjan's Algorithm is `O(v + e)` - where `v` is the number of vertices, and `e` the number of edges, in a graph.
* Space is `O(v)`

Below are implementations for finding strongly connected components in undirected adjacency list & adjacency matrix representations of graphs:

{% gist https://gist.github.com/jbolton209/2b633f00b83b6c8118dcb0658c6b9479 %}

As always, if you found any errors in this post please let me know!