Lecture5-Strongly Connected Components.ppt

《Lecture5-Strongly Connected Components.ppt》由会员分享，可在线阅读，更多相关《Lecture5-Strongly Connected Components.ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 2004 SDU 1 Lecture5-Strongly Connected Components 2004 SDU 2 Strongly Connected ComponentsA strongly connected component of a directed graph G=(V,E)is a maximal set V V of vertices such that for each pair of vertices u and v in V,they are reachable from each other.(1):Every pair of vertices in V ar

2、e reachable from each other;(2):Any other vertex set that contains V as a true subset does NOT satisfy(1).54132Is 1,2,3 a strongly connected component?Is 1,2,3,4 a strongly connected component?And 5?2004 SDU 3 The Strongly Connected Components Decomposition ProblemThe problem:Input:A directed graph

3、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.2004 SDU 4 ObservationFor each tree in a depth-first forest of a graph G:It contains all the vertices in the same SCC as the r

4、ootBut,it may also contain some that are not!1/8abfecgd2/73/45/69/1410/1112/13 2004 SDU 5 If we regard each SCC as one vertex,and sort them in topological sort1/8abe2/73/4f5/6c10/11g12/13d9/14How if we could know the topological sort of the SCCSand one representation of each SCCS?2004 SDU 6 If we li

5、st the SCCS in order of decreasing finishing times,is this a topological sort?YESHow to choose representations of SCCS?How to decide their order?Latest finished vertex in the SCC?1/8ab2/7e3/4f5/6g12/13d9/14c10/11If search in increasing f order,then e is searched first,but its SCC is not first finish

6、edIf we search in decreasing f order,just the same as first DFS 2004 SDU 7 How if reorder the edges and search in decreasing f order?1/8ab2/7e3/4f5/6g12/13d9/14c10/11 2004 SDU 8 ObservationsGiven a directed graph G=(V,E)G and GT have exactly the same strongly connected components,that is,u and v are

7、 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).2004 SDU 9 The Component Graph of GThe component graph GSCC=(VSCC,ESCC)

8、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 GThe edge set ESCC=(vi,vj)|G contains a directed edge(x,y)for some x Ci and some y CjIf we know all the SCCs of G,how can we construct t

9、he component graph GSCC?2004 SDU 10 A Key Property of GSCCThe 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 represen

10、t 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 11 An Example(a):The graph G with its SCCs shaded(c):The component graph GSCC=(VSCC,ESCC)of G(b):The transpos

11、e GT of G with SCCs shaded 2004 SDU 12 The AlgorithmTime Complexity:line 1,line 2,line 3:(V+E)line 4:O(V)How?2004 SDU 13 NotationsIf 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 finishing time of vertex set U,that is,t

12、he latest finishing time of any vertex in U.2004 SDU 14 A Key Property Related to SCCs and finishing timesLemma 22.14Let 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:CCuvCase 1:dC dCxy 2004 SDU 1

13、5 Can we order the fu for all vertices and search from the smallest fu?C1C2C3C4C5f(C1)f(C2)f(C3)2004 SDU 16 A CorollaryCorollary 22.15Let 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 finishin

14、g time is got from the first depth-searchProof:(u,v)ET (v,u)E,G and G have the same strongly connected components,Lemma 22.14 implies f(C)f(C2)f(C3)2004 SDU 18 Correctness of the AlgorithmTheorem 22.16STRONGLY-CONNECTED-COMPONENTS(G)correctly computes the strongly connected components of a directed

15、graph G.Proof:By induction on the number k of depth-first trees found in line 3,prove that the vertices of each tree form a strongly connected component,that is1.The vertex set V(T)of each depth-first tree contains all the vertices of a strongly connected component C 2.V(T)dose not contain any more

16、vertices other than those of CBasic step:k=0,it is trivially true.2004 SDU 19 Proof(Continued)C1C2Ck+2Ck+1Ck+3CmCkT1T2TkTk+1?2004 SDU 20 Proof(continued)Inductive step:Assume that each of the first k depth-first trees produced in line 3 is a strongly connected component.Consider the(k+1)st tree prod

17、uced.Let the root of the tree be vertex u,and let u be in strongly connected component C.By induction hypothesis,no vertices in C had been searched before,and since u has the biggest f among all the remaining vertices,fu=fC fC for any strongly connected component C other than C that has yet not been

18、 visited.2004 SDU 21 Proof(continued)1.At time du,all other vertices of C are white.By the white-path theorem,all other vertices of C are descendants of u in its depth-first tree.2.Moreover,by induction hypothesis and Corollary 22.15,any edge in GT that leaves C must point to SCC that have already b

19、een visited.Thus,no vertex in any SCC other than C will be a descendant of u during the depth-first search of GT.Thus,the vertices of the depth-first tree in GT that is rooted at u form exactly one strongly connected component.2004 SDU 22 A ConjectureProf Deaver:The algorithm for strongly connected

20、components can be simplified by using the original(instead of the transpose)graph in the second depth-first search and scanning the vertices in order of increasing finishing times.Is the conjecture correct?2004 SDU 23 The Answer1/102/53/46/97/8The reason is that the order of finishing times of verti

21、ces may not really reflect the order of finishing times of SCCs.CC 2004 SDU 24 Semi-connected GraphA directed graph G=(V,E)is semi-connected if for all pairs of vertices u,v V,we have u v(v is reachable from u)or v u(u is reachable from v)or both.How to determine whether or not a directed graph is s

22、emi-connected?(Exercise 22.5-7)2004 SDU 25 An ObservationGiven a directed graph G=(V,E),its strongly connected component graph is denoted as GSSC=(VSCC,ESCC).Then G is semi-connected if and only if for any pair of vertices u,v VSSC,either u is reachable from v or v is reachable from u(notice that th

23、ere can not be paths in both directions).2004 SDU 26 C1C2C3C4C5Notice that G SCC is acyclic.Suppose above is a topological sort of GSCC,then edges can only point from the left to right.Then C1 must reach each C2,C5,C2 must reach each C3,C5,C4 must reach C5.Then the red edges must exist,Vise versa.20

24、04 SDU 27 The Algorithm Outline1.Compute the strongly connected components of G.2.Construct the component graph GSCC of G.3.Topological Sort GSCC.4.Judge whether there is an edge from Ci to Ci+1,for 0im,if no,return“no”,where Ci is indexed by topological sort,and m is the number of SCCs.5.Return“yes

25、”.Time complexity:(V+E)2004 SDU 28 Another methodIn step 3,generate topological sort by using the method that each time finding a vertex of zero in-degree.Then G is semi-connected if and only if in each run,exactly one vertex of in-degree zero exists.Proof?simple by induction on#of SCCs.2004 SDU 29

26、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 30 RemarksUntil now,we have introduced Directed graphSingly connected graphSemi-connected graphStrongly connected graph 2004 SDU 31 ExercisesPage 175:22.4-3Page 172:22.3-12Page 180:22.5-5(22.1-4)2004 SDU 32