DEV Community

JB
JB

Posted on • Updated on

Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm

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

Resources:

  1. Video explanation
  2. Article explanation
  3. Implementation

Takeaways:

Strongly Connected Components

  • 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:

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

Discussion (0)