Lecture 13 Searching III 6.006 Fall 2009Lecture 13: Searching III: Topological SortLecture Overview: Search 3 of 3• BFS vs. DFS• job scheduling• topological sort• strongly connected componentsReadingsCLRS, Sections 22.4 and 22.5 (at a high level)Recall:• Breadth-First Search (BFS): level by level• Depth-First Search (DFS): backtrack as neccessary.• Both O(V + E) worst-case time =⇒ optimal• BFS computes shortest paths (min. ] edges)• DFS is a bit simpler & has useful properties1Lecture 13 Searching III 6.006 Fall 2009Job Scheduling:Given Directed Acylic Graph (DAG), where vertices represent tasks & edges representdependencies, order tasks without violating dep e ndenciesGHI489GHI1235A B C F5D E76Figure 1: Dependence GraphSourceSource = vertex with no incoming edges= schedulable at beginning (A,G,I)AttemptBFS from each source:- from A finds H,B,C,F- from D finds C, E, F- from G finds H}need to merge - costlyFigure 2: BFS-based Scheduling2Lecture 13 Searching III 6.006 Fall 2009Topological SortReverse of DFS finishing times (time at which vertex’s outgoing edges finished)We have a new field time that s tores the finishing time. To get a topological sort thatsolves the job scheduling problem, we simply run the DFS procedure below.parent = {s: None}time = {}ft = 0DFS-visit (V, Adj, s):for v in Adj [s]:if v not in parent:parent [v] = sDFS-visit (V, Adj, v)ft = ft + 1time[s] = ftTOPSORT (V, Adj)parent = { }for s in V:if s not in parent:parent [s] = NoneDFS-visit (V, Adj, s)Given the time dictionary, one can generate all keys from the dictionary and insert intoan array of length |V | indexed by the appropriate finishing time ft.In Figure 1, we run DFS-visit starting from vertex A and reach B, C and F . F finishesfirst, followed by C and B in the recursion. Next, we reach H from A. Then we are donewith A. DFS-visit beginning with A generates a depth-first tree with the vertices A, B,C, F , and H, and the edges (A, B), (B, C), (C, F ), and (A, H). We next run DFS-visitstarting with vertex D and reach vertex E. (Vertices C and F have already been visited.)This generates the depth-first tree with vertices D and E and with edge (D, E). We nextstart and end with vertex G, since we have already explored H. This generates the depth-first tree with the vertex G and no edges. Finally we start and end with vertex I. Thisgenerates the depth-first tree with the vertex I and no edges.The reverse order of the finishing times shown in Figure 1 is a topological sort.Note that the DFS procedure can be run on any graph – the graph does not have to bea DAG. We can compute finishing times for each vertex. These will depend on the orderedges are listed in Adj. Even if the graph is not a DAG, these finishing times are useful. Inparticular, they are useful in determining the strongly connected components (SCCs) of agraph.3Lecture 13 Searching III 6.006 Fall 2009Strongly Connected ComponentsC is an SCC of a directed graph G(V, E) if for every pair of vertices u and v in C there is apath from u to v and a path from v to u. The SCCs of a DAG correspond to the vertices,i.e., each vertex is an SCC. For graphs with cycles, SCCs are non-trivial to compute.For an algorithm to compute the SCCs of a graph, see CLRS Second/Third Edition22.5. You should understand the algorithm, but you are not responsible for the proof
View Full Document
Unlocking...