CompSci 100E39.1Graph Algorithmsÿ Topological Sort Produce a valid ordering of all nodes, given pairwiseconstraints 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 100E39.2Topological Sortÿ Topological Sort Algorithm 1. Find vertex with no incoming edges 2. Remove (updating incoming edge counts) and Output 3. Repeat 1 and 2 while vertices remain Complexity? ÿ Refine Algorithm Use priority queue? Complexity? ÿ What is the minimum number of semesters required? Develop algorithmCompSci 100E39.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 queue 2. For each adjacent vertex marked with *, ÿ process it, ÿ mark it with source distance + 1ÿ place it on the queue.CompSci 100E39.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 of queue 2. For each adjacent vertex marked with *, ÿ process it, ÿ mark it with source distance + 1ÿ place it on the queue. How do we get actual “Path”?CompSci 100E39.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 100E39.6Shortest Path (Weighted): DijkstraCompSci 100E39.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 of queue 2. For each adjacent vertex marked with *, ÿ process it, ÿ mark it with source distance + 1ÿ place it on the queue. How do we get actual “Path”?CompSci 100E39.8Other Graph Algorithmsÿ Traveling Salesman ÿ Spanning Treesÿ Paths with negative
View Full Document
Unlocking...