CSE310 Lecture 24 Strongly Connected Components Topological Sort Guoliang Xue Computer Science and Engineering Arizona State University 01 14 19 1 Topics of this lecture Strongly Connected Components Materials covered are in Sections 22 5 01 14 19 2 Strongly Connected Components Definitions A strongly connected component in a graph G V E is a maximal set of vertices C V such that every pair of vertices u and v in C are reachable from each other Before we present the algorithm that finds all strongly connected components we need to def Given a graph G V E the transpose graph of G is GT V ET where ET u v v u E In words ET consists edges of G with their directions reversed 01 14 19 3 Strongly Connected Components contd a Graph G Component graph 01 14 19 c d 13 14 11 16 1 10 12 15 3 4 2 7 5 6 e f g h a b c 14 Transpose GT b 16 10 8 9 d 9 15 4 7 6 e f g h Strongly connected components cd abc fg h 4 Finding Strongly Connected Components Strongly Connected Components G 1 Call DFS G to compute finishing times u fin for each vertex u in V 2 Construct GT 3 Call DFS GT but in the main loop of DFS consider choosing vertices in a specific order choosing vertices in order of decreasing u fin calculated in step 1 01 14 19 4 Output the vertices of each tree in the depth first forest formed in step 3 as a separate strongly connected component 5 Strongly Connected Component Lemma 22 13 Let C and C be distinct strongly connected components in a directed graph G V E Let u v be vertices in C and let u v be vertices in C If there is a path from u to u in G then there is no path from v to v in G Proof If there is also a path from v to v there would be a closed path from v to v to u to u to v which implies that all four vertices are in the same strongly connected components a contradiction 01 14 19 6 Strongly Connected Components Let S be a subset of vertices of V Define d S min d v v in S as the discovery time of S Define f S max f v v in S as the finish time of S 01 14 19 7 Strongly Connected Component Lemma 22 14 Let C and C be distinct strongly connected components in a directed graph G V E Suppose that there is an edge u v in E where u is in C and v is in C Then f C f C where f C is the largest finishing time in C Proof Consider two cases If d C d C then C is finished before u is finished If d C d C note that there is no edge from C to C then C is finished before C is discovered 01 14 19 8 Strongly Connected Component Corollary 22 15 Let C and C be distinct strongly connected components in a directed graph G V E Suppose that there is an edge u v in ET where u is in C and v is in C Then f C f C Proof Since v u is in E we have f C f C 01 14 19 9 Strongly Connected Component Theorem 22 16 Our algorithm correctly computes the strongly connected components Proof Let C1 be the component with the largest finishing time and let C 2 be any other component Starting from any verticex in C1 in GT we can visit all vertices in C1 but no vertices in C2 Therefore the tree will consists of exactly the vertices in C1 Repeating the process we get all the strongly connected components correctly 01 14 19 10 Topological Sort Linear Time Algorithm For each vertex v define in degree v We can compute the in degrees of all vertices in O V E time Color all vertices white If in degree v 0 insert v into a queue Q While Q is not empty delete v from Q For all edges v u do in degree u if in degree u 0 insert u into Q color v black If all vertices are black the order they are deleted from Q form a topological sort Otherwise the graph has a cycle 01 14 19 11 Finding a Cycle When the algorithm described on the previous slide ended with multiple nodes with no node with in degree 0 and some nodes with in degree larger than 0 there is no topological order In this case we can find a cycle How Mark all nodes with in degree larger than 0 as white Starting from any node u with in degree larger than 0 Color it black Since the in degree of u is larger than 0 there is a node v such that v u is an edge If v is black we have found a cycle If not we move on to node v Since there are a finite number of nodes the process ends 01 14 19 12 Finding a Cycle How can we find v from u We use the transpose graph In this case we can spend O n m time to either find a cycle or to find a topological order of the given graph 01 14 19 13
View Full Document
Unlocking...