7.5.3 Strong Components

REF.

Rao S. Kosaraju. Unpublished. 1978.

REF.

Robert E. Tarjan. Depth first search and linear graph algorithms. SIAM Journal on Computing, Volume 1, Number 2, pp. 146-160, 1972.

• A strongly connected component of a digraph is a maximal set of vertices in which there is a path from any one vertex to any other vertex in the set. For an example, see Figure 7.15.

 

 

Figure 7.15: Strong components of a digraph


• Let G = (V, E) be a digraph. We can partition V into equivalence classes V_i, 1 $\leq$i $\leq$r, such that vertices v and w are equivalent if there is a path from v to w and a path from w to v.


Let E_i, 1 $\leq$i$\leq$r, be the set of arcs with head and tail both in V_i.

Then the graphs (V_i, E_i) are called the strong components of G.

A digraph with only one strong component is said to be strongly connected.

• Depth-first-search can be used to efficiently determine the strong components of a digraph.
• Kosaraju's (1978) algorithm for finding strong components in a graph:

1.

Perform a DFS of G and number the vertices in order of completion of the recursive calls.

2.

Construct a new directed graph G_r by reversing the direction of every arc in G.

3.

Perform a DFS on G_r starting the search from the highest numbered vertex according to the numbering assigned at step 1. If the DFS does not reach all vertices, start the next DFS from the highest numbered remaining vertex.

4.

Each tree in the resulting spanning forest is a strong component of G.

Figure 7.16: Step 1 in the strong components algorithm

 
 

Figure 7.17: Step 3 in the strong components algorithm

Example: See Figures 7.16 and 7.17

Proof of Kosaraju's Algorithm

• First we show: If v and w are vertices in the same strong component, then they belong to the same spanning tree in the DFS of G_r.

v and w in the same strong component

 

$$\Longrightarrow$$$$\exists$$$$\mbox{a path in $G$ }$$	from v to w and
	from w to v
$$\Longrightarrow$$$$\exists$$$$\mbox{a path in $G$ }$$	from w to v and
	from v to w

Let us say in the DFS of G_r we start at some x and reach vor w. Since there is a path from v to w and vice versa, v and wwill end up in the same spanning tree (having root x).
• Now we show: If v and w are in the same spanning tree in the DFS of G_r, then, they are in the same strong component of G.


Let x be the root of the spanning tree containing v and w.  

$$\Longrightarrow$$$$\mbox{$v$\space is a descendant of}$$	x
$$\Longrightarrow$$$$\exists$$$$\mbox{a path in $G_{r}$ }$$	from x to v
$$\Longrightarrow$$$$\exists$$$$\mbox{a path in $G$ }$$	from v to x

In the DFS of G_r, vertex v was still unvisited when the DFSat x was initiated (since x is the root)  

$$\Longrightarrow$$	x$$\mbox{$x$\space has a higher number than $v$ }$$
	$$\mbox{(since $DFS$\space of $G_{r}$\space starts from highest numbered (remaining)vertex)}$$.
$$\Longrightarrow$$	$$\mbox{In the $DFS$\space of $G$ , the recursivecall at $v$\space terminated before the}$$
	$$\mbox{recursive call at $x$ did. (due to the numbering done in step 1)}$$

$$\leadsto$$ (7.16) +

$$\mbox{Recursive call at $v$\space terminatesbefore that of $x$\space in $G$ }$$ (7.17)

In the DFS of G, there are two possibilities.

$$\mbox{Search of $v$\space occurs before $x$ }$$ 1) (7.18)

$$\mbox{Search of $x$ occurs before $v$ }$$ 2) (7.19)

 

(1),(3)	$$\Longrightarrow$$$$\mbox{$DFS$\space of $v$\space ... invokes $DFS$\space of $x$ back to $v$ }$$.
	$$\Longrightarrow$$$$\mbox{search at $x$\space would start and endbefore the search starts at $v$\space ends}$$.
	$$\Longrightarrow$$$$\mbox{recursivecall at $v$\space terminates after the call at $x$\space contradicts (2)}$$.
	$$\Longrightarrow$$$$\mbox{search of $x$\space occurs before $v$ }$$.
(4),(2)	$$\Longrightarrow$$$$\mbox{$v$\space is visited during the search of $x$ }$$.
	$$\Longrightarrow$$$$\mbox{$v$\space is descendant of $x$ }$$.
	$$\Longrightarrow$$$$\mbox{$\exists$\space a path from $x$\space to $v$ }$$.
	$$\Longrightarrow$$$$\mbox{$x$\space and$v$\space are in the same strong component}$$.
	Similarly,$$\mbox{$x$ and $w$\space are in the same strong component}$$.
	$$\Longrightarrow$$$$\mbox{Similarly, $v$\space and $w$\space are in the same strong component}$$.