loading...

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

jjb profile image JB Updated on ・2 min read

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!

Posted on by:

Discussion

markdown guide