算法课件Lecture4章节.pptVIP

Strongly Connected 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, vertices u and v are reachable from each other. The Strongly Connected Components Decomposition Problem The problem: Input: A directed graph G = (V, E). Output: All the strongly connected components of G. In practice, many algorithms that work with directed graphs begin with a strongly connected components decomposition.(exercise 22.3-12) Observations Given a directed graph G = (V, E) G and GT have exactly the same strongly connected components, that is, u and v are reachable from each other in G if and only if they are reachable from each other in GT. Note: GT is the transpose of G, i.e., GT=(V, ET), where ET={(v,u)| (u,v)?E}. Given an adjacency-list representation of G, the time to create GT is ?(V + E). The Component Graph of G The component graph GSCC = (VSCC, ESCC) of a directed graph G = (V, E) is defined as follows: Suppose that G has strongly connected components C1, C2, …, Ck: the vertex set VSCC = {vi | vi corresponds to component Ci of G} the edge set ESCC = {(vi, vj) | G contains a directed edge (x, y) for some x ? Ci and some y ? Cj} If we know all the SCCs of G, how can we construct the component graph GSCC? A Key Property of GSCC The component graph GSCC = (VSCC, ESCC) is a directed acyclic graph. (Lemma 22.13) Proof. Suppose for the contrary that GSCC is cyclic, that is, there exist two vertices u, v ?VSCC such that u and v are reachable from each other. Suppose u and v represent the two strongly connected components Cu and Cv of G, then vertices in Cu and Cv are reachable from each other, which contradicts with the definition of strongly connected component. Search SCCS in reverse topological sort order An Example The Algorithm Notations If U ? V, define d[U] = minu?U{d[u]}, the discovery time of vertex set U, that is, the earliest discovery time of any vertex in U;