CSE310 Lecture 24 Strongly Connected Components Topological SortTopics of this lecturePowerPoint PresentationSlide 4Slide 5Strongly Connected ComponentStrongly Connected ComponentsSlide 8Slide 9Slide 10Topological Sort—Linear Time AlgorithmFinding a CycleSlide 13101/14/19CSE310 Lecture 24Strongly Connected ComponentsTopological SortGuoliang XueComputer Science and EngineeringArizona State University201/14/19Topics of this lectureStrongly Connected ComponentsMaterials covered are in Sections 22.5301/14/19Strongly Connected ComponentsDefinitionsA 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.401/14/19Strongly Connected Components (contd.)13/1412/1511/163/48/95/6a b de f h1/102/7cgGraphGabcfgcdhComponentgraphStronglyconnectedcomponentsa b de f h141516496107cgTransposeGT501/14/19Strongly-Connected-Components(G)1 Call DFS(G) to compute finishing times u.fin for each vertex u in V;2 Construct GT3 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;4 Output the vertices of each tree in the depth-first forest formed in step 3 as a separate strongly connected component.Finding Strongly Connected Components601/14/19Strongly Connected ComponentLemma 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.701/14/19Strongly Connected ComponentsLet 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.801/14/19Strongly Connected ComponentLemma 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.901/14/19Strongly Connected ComponentCorollary 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).1001/14/19Strongly Connected ComponentTheorem 22.16. Our algorithm correctly computes the strongly connected components.Proof. Let C1 be the component with the largest finishing time and let C2 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.1101/14/19Topological Sort—Linear Time AlgorithmFor 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) doin-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.1201/14/19Finding a CycleWhen 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.1301/14/19Finding a CycleHow 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
View Full Document
Unlocking...