Directed Graph AlgorithmsReadingsTopological SortPowerPoint PresentationSlide 5Slide 6Paths and CyclesOnly acyclic graphs can be topo. sortedSlide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Calculate In-degreesSlide 22Slide 23Topological Sort AlgorithmSome DetailTopological Sort AnalysisSlide 27Recall Path cost ,Path lengthShortest Path ProblemsWhy study shortest path problems?Unweighted Shortest PathBreadth-First Search SolutionBreadth-First Search Alg.Example: Shortest Path lengthExample (ct’d)Slide 36Slide 37Slide 38Slide 39What if edges have weights?Dijkstra’s Algorithm for Weighted Shortest PathBasic Idea of Dijkstra’s AlgorithmDirected Graph AlgorithmsCSE 373Data StructuresLecture 1412/26/03 Digraphs - Lecture 14 2Readings•Reading ›Sections 9.2 , 9.3 and 10.3.412/26/03 Digraphs - Lecture 14 3Topological Sort321143322326341370378401421Problem: Find an order inwhich all these courses can be taken.Example: 142  143  378 370  321  341  322 326  421  401In order to take a course, you must take all of its prerequisites first14212/26/03 Digraphs - Lecture 14 4Given a digraph G = (V, E), find a linear ordering of its vertices such that: for any edge (v, w) in E, v precedes w in the orderingABCFDETopological Sort12/26/03 Digraphs - Lecture 14 5ABCFDEEA DFB CAny linear ordering in whichall the arrows go to the rightis a valid solutionTopo sort - good exampleNote that F can go anywhere in this list because it is not connected.Also the solution is not unique.12/26/03 Digraphs - Lecture 14 6ABCFDEDA EFB CAny linear ordering in whichan arrow goes to the leftis not a valid solutionTopo sort - bad exampleNO!12/26/03 Digraphs - Lecture 14 7Paths and Cycles•Given a digraph G = (V,E), a path is a sequence of vertices v1,v2, …,vk such that:›(vi,vi+1) in E for 1 < i < k›path length = number of edges in the path›path cost = sum of costs of each edge •A path is a cycle if :›k > 1; v1 = vk •G is acyclic if it has no cycles.12/26/03 Digraphs - Lecture 14 8Only acyclic graphs can be topo. sorted•A directed graph with a cycle cannot be topologically sorted.ABCFDE12/26/03 Digraphs - Lecture 14 9Step 1: Identify vertices that have no incoming edges• The “in-degree” of these vertices is zeroABCFDETopo sort algorithm - 112/26/03 Digraphs - Lecture 14 10Step 1: Identify vertices that have no incoming edges• If no such vertices, graph has only cycle(s) (cyclic graph)• Topological sort not possible – Halt.ABCDExample of a cyclic graphTopo sort algorithm - 1a12/26/03 Digraphs - Lecture 14 11Step 1: Identify vertices that have no incoming edges• Select one such vertexABCFDESelectTopo sort algorithm - 1b12/26/03 Digraphs - Lecture 14 12ABCFDEStep 2: Delete this vertex of in-degree 0 and all its outgoing edges from the graph. Place it in the output.Topo sort algorithm - 2A12/26/03 Digraphs - Lecture 14 13ABCFDERepeat Step 1 and Step 2 until graph is emptySelectContinue until done12/26/03 Digraphs - Lecture 14 14ABCFDEBSelect B. Copy to sorted list. Delete B and its edges.B12/26/03 Digraphs - Lecture 14 15ACFDEB CSelect C. Copy to sorted list. Delete C and its edges.C12/26/03 Digraphs - Lecture 14 16AFDEB CDSelect D. Copy to sorted list. Delete D and its edges.D12/26/03 Digraphs - Lecture 14 17AFEB CDE FSelect E. Copy to sorted list. Delete E and its edges.Select F. Copy to sorted list. Delete F and its edges.E, F12/26/03 Digraphs - Lecture 14 18A B CDE FDoneABCFDE12/26/03 Digraphs - Lecture 14 19ABCFDE245543123456Assume adjacency listrepresentationImplementationA B C D E F1 2 3 4 5 6Translationarrayvalue next12/26/03 Digraphs - Lecture 14 20010221In-Degree array; or add a field to array ACalculate In-degrees245543123456AD12/26/03 Digraphs - Lecture 14 21Calculate In-degreesfor i = 1 to n do D[i] := 0; endforfor i = 1 to n do x := A[i]; while x  null do D[x.value] := D[x.value] + 1; x := x.next; endwhileendfor12/26/03 Digraphs - Lecture 14 22Key idea: Initialize and maintain a queue (or stack)of vertices with In-Degree 01Queue6123645Maintaining Degree 0 Vertices010221245543123456AD12/26/03 Digraphs - Lecture 14 23After each vertex is output, when updating In-Degree array, enqueue any vertex whose In-Degree becomes zero1Queue6Output2dequeueenqueue123645Topo Sort using a Queue (breadth-first)000121245543123456AD12/26/03 Digraphs - Lecture 14 24Topological Sort Algorithm1. Store each vertex’s In-Degree in an array D2. Initialize queue with all “in-degree=0” vertices3. While there are vertices remaining in the queue:(a) Dequeue and output a vertex(b) Reduce In-Degree of all vertices adjacent to it by 1(c) Enqueue any of these vertices whose In-Degree became zero4. If all vertices are output then success, otherwise there is a cycle.12/26/03 Digraphs - Lecture 14 25Some DetailMain Loopwhile notEmpty(Q) do x := Dequeue(Q) Output(x) y := A[x]; while y  null do D[y.value] := D[y.value] – 1; if D[y.value] = 0 then Enqueue(Q,y.value); y := y.next; endwhileendwhile12/26/03 Digraphs - Lecture 14 26Topological Sort Analysis•Initialize In-Degree array: O(|V| + |E|)• Initialize Queue with In-Degree 0 vertices: O(|V|)• Dequeue and output vertex:›|V| vertices, each takes only O(1) to dequeue and output: O(|V|) • Reduce In-Degree of all vertices adjacent to a vertex and Enqueue any In-Degree 0 vertices:› O(|E|) •For input graph G=(V,E) run time = O(|V| + |E|)›Linear time!12/26/03 Digraphs - Lecture 14 27After each vertex is output, when updating In-Degree array, push any vertex whose In-Degree becomes zero1Stack2Output6poppush123645Topo Sort using a Stack (depth-first)000121245543123456AD12/26/03 Digraphs - Lecture 14 28Recall Path cost ,Path length•Path cost: the sum of the costs of each edge•Path length: the number of edges in the path›Path length is the unweighted path costSeattleSan FranciscoDallasChicagoSalt Lake City42223223length(p) = 5cost(p) = 1112/26/03 Digraphs - Lecture 14 29Shortest Path Problems•Given a graph G = (V, E) and a “source” vertex s in V, find the minimum cost paths from s to every vertex in V •Many variations:›unweighted vs. weighted›cyclic vs. acyclic›pos. weights only vs. pos. and neg. weights ›etc12/26/03 Digraphs - Lecture 14 30Why study shortest path problems?•Traveling on a budget: What is the cheapest airline schedule from Seattle to city X?•Optimizing routing of packets on the