In the realm of computer science and discrete mathematics, graphs serve as a fundamental tool for modeling and solving real-world problems. Strongly Connected Components (SCCs) play a crucial role in understanding the structure of directed graphs. In this article, we'll delve into finding SCCs using Depth First Search (DFS), exploring technical details, examples, and a step-by-step explanation of the algorithm.

Introduction to Strongly Connected Components

A directed graph is termed strongly connected if there is a path from every vertex to every other vertex. An SCC is a maximal subgraph that is strongly connected, i.e., every vertex within the subgraph is reachable from every other vertex. Identifying SCCs reveals essential insights into the modularity and stability of systems modeled by graphs, such as social networks, web graphs, and more.

The Role of Depth First Search in Finding SCCs

DFS is a cornerstone graph traversal technique that aids in identifying SCCs. It leverages the idea of traversing as far as possible down a branch before backtracking, effectively exploring all vertices along edges, and keeping track of discovery and finishing times.

Algorithm: Tarjan’s Algorithm for SCCs

Tarjan's algorithm is a classic method for finding SCCs using a DFS-based approach. It operates efficiently with a time complexity of $O(V + E)$, where $V$ is the number of vertices and $E$ is the number of edges. Here is an outline of Tarjan's algorithm:

1. Initialization:
   • Assign a `discovery` time and a `low` value to each vertex. Initially, set both these values to -1.
   • Use a stack to store the nodes and a boolean array to know which nodes are part of the current SCC.
2. DFS Traversal:
   • Start DFS from any vertex not yet visited.
   • As you traverse, update `discovery` and `low` values for each vertex.
   • If a vertex can reach an ancestor, update its `low` value.
3. Tracking SCCs:
   • If the `low` value of a node equals its `discovery` value, it's the root of an SCC.
   • Every node in the stack up to this node forms the SCC, and they're popped from the stack.

Example

Consider the following directed graph:

• Start DFS from node A:
  • `discovery(A) = low(A) = 1`
• Visit B:
  • `discovery(B) = low(B) = 2`
• Visit C and backtrack to B:
  • `discovery(C) = low(C) = 3, low(B) = min(low(B), low(C)) = 2`
• Visit E, D, and backtrack to B:
  • After processing E and D:
    • `low(E) = min(low(E), low(D)) = 4, low(B) = min(low(B), low(E)) = 2`
• Visit F and backtrack to A:
  • `discovery(F) = low(F) = 6, low(A) = min(low(A), low(F)) = 1`
  • Perform a DFS and store vertices in a stack based on their finishing times.
  • Reverse the directions of all arcs to obtain the transpose.
  • Perform DFS based on the order of their finishing times in the transposed graph to identify SCCs.