CompSci 100E38.1Graph Algorithmsÿ Topological Sortþ Produce a valid ordering of all nodes, given pair-wiseconstraintsþ Solution usually not uniqueþ When is solution impossible?ÿ Topological Sort Example: Getting an AB in CPSþ Express prerequisite structureþ This example, CPS courses only: 6, 100, 104, 108, 110, 130þ Ignore electives or outside requirements (can add later)CompSci 100E38.2Topological Sortÿ Topological Sort Algorithm1. Find vertex with no incoming edges2. Remove (updating incoming edge counts) and Output3. Repeat 1 and 2 while vertices remainþ Complexity?ÿ Refine Algorithmþ Use priority queue?þ Complexity?ÿ What is the minimum number of semesters required?þ Develop algorithmCompSci 100E38.3Shortest Path (Unweighted)þ Mark all vertices with infinity (*) exec. starting vertex with 0þ Place starting vertex in queueþ Repeat until queue is empty:1. Remove a vertex from front of queue2. For each adjacent vertex marked with *,ÿ process it,ÿ mark it with source distance + 1ÿ place it on the queue.CompSci 100E38.4Shortest Path (Unweighted)þ Mark all vertices with infinity (*)þ Mark starting vertex with 0þ Place starting vertex in queueþ Repeat until queue is empty:1. Remove a vertex from front ofqueue2. For each adjacent vertex markedwith *,ÿ process it,ÿ mark it with source distance+1ÿ place it on the queue.How do we get actual “Path”?CompSci 100E38.5Shortest Path (Weighted): Dijkstraþ Unmark all vertices and give infinite weightþ Set weight of starting vertex at 0 and place in priority queueþ Repeat until priority queue is empty:1. Remove a vertex from priority queueÿ Process and mark (weight now permanent)2. For each adjacent unmarked vertexÿ Set weight at lesser of current weight and(source weight + path weight)ÿ (This may involve reducing previous weight setting)ÿ Place in priority queue (if not there already)CompSci 100E38.6Shortest Path (Weighted): DijkstraCompSci 100E38.7Shortest Path (Weighted): Dijkstraþ Mark all vertices with infinity (*)þ Mark starting vertex with 0þ Place starting vertex in queueþ Repeat until queue is empty:1. Remove a vertex from front ofqueue2. For each adjacent vertex markedwith *,ÿ process it,ÿ mark it with source distance+1ÿ place it on the queue.How do we get actual “Path”?CompSci 100E38.8Other Graph Algorithmsÿ Traveling Salesmanÿ Spanning Treesÿ Paths with negative
View Full Document
Unlocking...