算法课件Lecture4章节

1、 2004 SDU 1,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.,Is 1,2,3 a strongly connected component?,Is 1,2,3,4 a strongly connected component? And 5?, 2004 SDU 2,The Strongly Connected Components Decomposition Problem,The problem: Input: A directed graph G = (V, E). Output: All the strongly connected components of G. In p

2、ractice, many algorithms that work with directed graphs begin with a strongly connected components decomposition.(exercise 22.3-12), 2004 SDU 3,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

3、GT is (V + E)., 2004 SDU 4,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?, 2004 SDU 5,A Key Property of GSCC,The component graph GSC

4、C = (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., 2004 SDU 6,Search SCCS in reverse topological sort order,Suppose we search the graph

5、 in the order:C5, C4, C3, C2,C1, then How to decide the topological sort order of the SCCs?, 2004 SDU 7,An Example,(a): The graph G with its SCCs shaded,(c): The component graph GSCC = (VSCC, ESCC) of G,(b): The transpose GT of G with SCCs shaded, 2004 SDU 8,The Algorithm,Time Complexity: line 1, line 2, line 3: (V + E) line 4: O(V + E), 2004 SDU 9,Notations,If U V, define dU = minuUdu, the discovery time of vertex set U, that is, the earliest discovery time of any vertex in U; fU = maxuUfu, the

6、 finishing time of vertex set U, that is, the latest finishing time of any vertex in U., 2004 SDU 10,A Key Property Related to SCCs And finishing times,Lemma 22.14 Let C and C be distinct strongly connected components in directed graph G = (V, E). Suppose that there is an edge (u, v) E, where u C and v C. Then f(C) f(C). Proof:,C,C,u,v,Case 1: dC dC,x,y, 2004 SDU 11,Can we order the fu for all vertices and search from the smallest fu?,f(C1)f(C2)f(C3), 2004 SDU 12,A Corollary,Corollary 22.15 Let

7、C and C be distinct strongly connected components in directed graph G = (V, E). Suppose that there is an edge (u, v) ET, where u C and v C. Then f(C) f(C). Here, the finishing time is got from the first depth-search Proof: (u, v) ET (v, u) E, G and G has the same strongly connected components, Lemma 22.14 implies f(C) f(C)., 2004 SDU 13,C1,C2,C3,C4,C5,Can we search from the largest fu in GT?,f(C1)f(C2)f(C3), 2004 SDU 14,Correctness of the Algorithm,Theorem 22.16 STRONGLY-CONNECTED-COMPONENTS(G)

8、correctly computes the strongly connected components of a directed graph G. Proof: (Prove by induction on the number of depth-first trees found in the depth-first search of GT in line 3 that the vertices of each tree form a strongly connected component, that is, (1)that the set V(T)of vertices of each depth-first tree contains the vertices of a strongly connected component C (2)V(T) dose not contain any more vertices other than those of C.) Basic step: k = 0, it is trivially true., 2004 SDU 15,Proof (Continued),C1,C2,Ck+2,Ck+1,Ck+3,Cm,Ck,T1,T2,Tk,Tk+1,?, 2004 SDU 16,Proof (Continued),Inductive step: assume that each of the first k depth-first trees produced in line 3 is a strongly connected component, and we consider the (k+1)st tree produced. Let the root of the tr

《算法课件Lecture4章节》由会员E****分享，可在线阅读，更多相关《算法课件Lecture4章节》请在金锄头文库上搜索。