Graph Algorithm #1: Topological Sort

1R. Rao, CSE 326 Lecture 20: Topo-Sort and Dijkstra’s Greedy Idea ✦ Items on Today’s Lunch Menu: ➭ Topological Sort (ver. 1 & 2): Gunning for linear time… ➭ Finding Shortest Paths ➧ Breadth-First Search ➧ Dijkstra’s Method: Greed is good! ✦ Covered in Chapter 9 in the textbook Some slides based on: CSE 326 by S. Wolfman, 2000 2R. Rao, CSE 326 Graph Algorithm #1: Topological Sort 321 143 142 322 326 341 370 378 401 421 Problem: Find

an order in which all these courses can be taken. Example: 142 143 378 370 321 341 322 326 421 401 3R. Rao, CSE 326 Topological Sort Definition Topological sorting problem: given digraph G = (V, E) , find a linear ordering of vertices such that: for all edges (v, w) in E, v precedes w in the ordering A B C F D E 4R. Rao, CSE 326 Topological Sort Topological sorting problem: given digraph G = (V, E) , find a linear ordering of vertices such that: for any edge (v, w) in E, v precedes w in the ordering A B C F D E EA DFB C Any linear ordering in which all the arrows go to the right is a valid solution 5R. Rao, CSE 326 Topological Sort Topological sorting problem: given digraph G = (V, E) , find a linear ordering of vertices such that: for any edge (v, w) in E, v precedes w in the ordering A B C F D E FA DEB C Not a valid topological sort! 6R. Rao, CSE 326 Step 1: Identify vertices that have no incoming edge The “in-degree” of these vertices is zero A B C F D E Topological Sort Algorithm 7R. Rao, CSE 326 Step 1: Identify vertices that have no incoming edge If no such edges, graph has cycles (cyclic graph) A B C D Topological Sort Algorithm Example of a cyclic graph: No vertex of in-degree 0 8R. Rao, CSE 326 Step 1: Identify vertices that have no incoming edges Select one such vertex A B C F D E Topological Sort Algorithm Select 9R. Rao, CSE 326 A B C F D E Topological Sort Algorithm Step 2: Delete this vertex of in-degree 0 and all its outgoing edges from the graph. Place it in the output. 10R. Rao, CSE 326 A B C F D E Topological Sort Algorithm Repeat Steps 1 and Step 2 until graph is empty Select 11R. Rao, CSE 326 Topological Sort Algorithm Repeat Steps 1 and Step 2 until graph is empty A B C F D E Select 12R. Rao, CSE 326 Topological Sort Algorithm Repeat Steps 1 and Step 2 until graph is empty C D E A B F Select 13R. Rao, CSE 326 Topological Sort Algorithm Repeat Steps 1 and Step 2 until graph is empty C D EA B...

Website: www.cs.washington.edu | Filesize: -
No of Page(s): 19
Download Graph Algorithm #1: Topological Sort - Computer Science ....pdf