CSCE 411 Lecture 19

Lecture Slides

« previous | Wednesday, October 10, 2012 | next »

Strongly Connected Components

A directed graph is strongly connected iff you can go from any node to any other node

A strongly connected component (SCC) is a maximal set of nodes with a directed path between every pair of nodes.

For example: Packaging software modules

• Construct directed graph of which modules call which other modules
• SCC is a set of mutually interacting modules
• Put those modules in the same SCC

Algorithm

DFS tells us which nodes are reachable from roots of individual trees, but we need information about the "other direction": is the root reachable from its descendants? (reverse direction of edges)

1. Call DFS($G$) to compute finishing times ($O(V+E)$)
2. Compute $G^T$ (transpose of adjacency matrix graph; reverse direction of all edges) ($O(V+E)$; assuming adjacency list)
3. Call DFS($G^T$), considering nodes in decreasing order of finishing times ($O(V+E)$)
4. Each tree from (3) is a separate SCC of $G$

Total running time: $O(V+E)$

Example

Finish times for step 1:

1 2 3     4 5     6 7 8     9 10 11 12 13    14 15 16
| | '--c--' '--d--' | '--e--'  |  |  |  '--h--'  |  |
| '--------b--------'          |  |  '-----g-----'  |
'---------------a--------------'  '--------f--------'

Thus order of nodes for step 3 is: f, g, h, a, e, b, d, c

Finish times for step 2:

1 2 3     4 5 6 7 8     9 10 11 12    13 14 15    16
| | '--g--' | | | '--e--'  |  |  '--c--'  |  '--d--'
| '----h----' | '----a-----'  '-----b-----'
'------f------'

Thus {f, h, g}, {a,e}, {b,c}, and {d} are SCCs

Correctness

Let $C_i$ represent a strongly connected component in $G$

Draw a graph using $C_i$'s as vertices, and edges from $C_i$ to $C_j$ iff $G$ has an edge from a vertex in $C_i$ to a vertex in $C_j$.

The resulting graph does not have any cycles.

Proof

Let $d(C)$ be the earliest discovery time of any node in $C$, and likewise let $f(C)$ be the latest finishing time in $C$.

We claim that $f(C^{\prime })>f(C)$ if there is an edge in $G$ from component $C^{\prime }$ to $C$

Case 1: $d(C^{\prime })<d(C)$. Suppose $x$ is the first node discovered in $C^{\prime }$. DFS would take all nodes in $C^{\prime }$ and $C$ as descendents of $x$, so $x$ is the last node in $C^{\prime }$ to finish and finishes after all nodes in $C$. Thus $f(C^{\prime })>f(C)$

Case 2: $d(C^{\prime })>d(C)$. Suppose $y$ is the first node discovered in $C$. DFS would accept all nodes in $C$ as descendents of $y$, so $y$ is the last node to finish. Since $C^{\prime }\to C$, no node in $C^{\prime }$ is reachable from $y$, so $y$ finishes before any node in $C^{\prime }$ is discovered. Thus $f(C^{\prime })>f(C)$

Induction on number of trees in step 3 (Calling DFS on $G^T$): The first $k$ trees found constitute $k$ SCCs of $G$.

Basis: $k=0$, no work to do.

Induction: Assume the first

$k$

trees constructed in step 3 correspond to

$k$

SCCs. Consider the

$(k+1)$

^st tree: (let

$u$

be the root of the

$(k+1)$

^st tree)

$u$

is part of SCC

$C$

, and by inductive hypothesis,

$C$

is one of

$k$

SCCs already found, and all nodes in

$C$

are unvisited when

$u$

is discovered.

Q.E.D.