Strongly Connected Components

Strongly connected components: We now consider a classic application of depth-first search: decomposing a directed graph into its strongly connected components. This section shows how to do this decomposition using two depth-first searches. Many algorithms that work with directed graphs begin with such a decomposition. After decomposition, the algorithm is run separately on each strongly connected component. The solutions are then combined according to the structure of connections between components.

A strongly connected component of a directed graph G = (V, E) is a maximal set of vertices C V such that for every pair of vertices u and v in C, we have both and ; that is, vertices u and v are reachable from each other. Figure 22.9 shows an example.

Figure 22.9: (a) A directed graph G. The strongly connected components of G are shown as shaded regions. Each vertex is labeled with its discovery and finishing times. Tree edges are shaded. (b) The graph GT, the transpose of G. The depth-first forest computed in line 3 of STRONGLY-CONNECTED-COMPONENTS is shown, with tree edges shaded. Each strongly connected component corresponds to one depth-first tree. Vertices b, c, g, and h, which are heavily shaded, are the roots of the depth-first trees produced by the depth-first search of GT. (c) The acyclic component graph GSCC obtained by contracting all edges within each strongly connected component of G so that only a single vertex remains in each component.

Our algorithm for finding strongly connected components of a graph G = (V, E) uses the transpose of G. Given an adjacency-list representation of G, the time to create GT is O(V E). It is interesting to observe that G and GT have exactly the same strongly connected components: u and v are reachable from each other in G if and only if they are reachable from each other in GT. Figure 22.9(b) shows the transpose of the graph in Figure 22.9(a), with the strongly connected components shaded.

The following linear-time (i.e., Θ(V E)-time) algorithm computes the strongly connected components of a directed graph G = (V, E) using two depth-first searches, one on G and one on GT.

1  call DFS (G) to compute finishing times f[u] for each vertex u
2  compute GT
3  call DFS (GT), but in the main loop of DFS, consider the vertices
          in order of decreasing f[u] (as computed in line 1)
4  output the vertices of each tree in the depth-first forest formed in line 3 as a
          separate strongly connected component

The idea behind this algorithm comes from a key property of the component graph GSCC = (VSCC, ESCC), which we define as follows. Suppose that G has strongly connected components C1, C2,..., Ck. The vertex set VSCC is {v1, v2,..., vk}, and it contains a vertex vi for each strongly connected component Ci of G. There is an edge (vi, vj) ESCC if G contains a directed edge (x, y) for some x Ci and some y Cj. Looked at another way, by contracting all edges whose incident vertices are within the same strongly connected component of G, the resulting graph is GSCC. Figure 22.9(c) shows the component graph of the graph in Figure 22.9(a).

The key property is that the component graph is a dag, which the following lemma implies. Articulation points, bridges, and biconnected components

Let G = (V, E) be a connected, undirected graph. An articulation point of G is a vertex whose removal disconnects G. A bridge of G is an edge whose removal disconnects G. A biconnected component of G is a maximal set of edges such that any two edges in the set lie on a common simple cycle. Figure 22.10 illustrates these definitions. We can determine articulation points, bridges, and biconnected components using depth-first search. Let Gπ = (V, Eπ) be a depth-first tree of G.

Figure 22.10: The articulation points, bridges, and biconnected components of a connected, undirected graph for use in Problem 22-2. The articulation points are the heavily shaded vertices, the bridges are the heavily shaded edges, and the biconnected components are the edges in the shaded regions, with a bcc numbering shown.
  1. Prove that the root of Gπ is an articulation point of G if and only if it has at least two children in Gπ.

  2. Let v be a nonroot vertex of Gπ. Prove that v is an articulation point of G if and only if v has a child s such that there is no back edge from s or any descendant of s to a proper ancestor of v.

  3. Let  

  4. Show how to compute low[v] for all vertices v V in O(E) time.

  5. Show how to compute all articulation points in O(E) time.

  6. Prove that an edge of G is a bridge if and only if it does not lie on any simple cycle of G.

  7. Show how to compute all the bridges of G in O(E) time.

  8. Prove that the biconnected components of G partition the nonbridge edges of G.

  9. Give an O(E)-time algorithm to label each edge e of G with a positive integer bcc[e] such that bcc[e] = bcc[e] if and only if e and e are in the same biconnected component.