Strongly Connected Components - rFronteddu/general_wiki GitHub Wiki

A strongly connected component (SCC) of a directed graph G=(V, E) is a maximal subgraph where every pair of vertices is mutually reachable; i.e., for any two vertices u and v in the SCC, both u → v and v → u exist. This requires bidirectional connectivity, unlike regular connected components in undirected graphs.

To find SCCs, we can use the transpose of a graph G, denoted $$G^{T}$$ = (V, $E^{T}$ ), where the direction of all edges is reversed.

Algorithm to find SCCs

stronglyConnectedComponents(G)
    run DFS(G) to compute finishing times for each vertex
    compute G^T
    run DFS(G^T), processing vertices in decreasing order of their finishing times from the first DFS
    Each DFS tree in G^T corresponds to an SCC in G.

The result is a condensation graph of G, where each SCC is represented as a single vertex, and there is a directed edge between two SCCs if there is an edge between any vertex in one SCC and any vertex in the other. This condensation graph is always a Directed Acyclic Graph (DAG).

The condensation of $G^{scc}$ of this graph would look like 4 nodes:

• abe -> cd and fg
• fg -> h
• cd -> fg and h