Graph algorithms Coming up Useful data structures Heaps Priority Queues ( Chap 6) Disjoint Sets Chap 21) Graph Algorithms Elementary Graph Algorithms (Chap 22) Graph Representations Breadth-first search o Depth-first search e Topological sort Minimum Spanning Trees Chap 23 Kruskal's algorithm, Prims algorithm Single-Source Shortest Paths Chap 24 Bellman- Ford algorithm o Algorithm for Directed Acyclic Graph o Dijkstra's algorithm Al-Pairs Shortest Paths Chap 25) Shortest Paths by repeated squaring o Floyd-Warshall Alg. Johnsons Alg CS3381 Des Anal of Alg(2001-2002 SemA) City Univ of HK /Dept of CS Helena Wong http://www.cs.cityu.edu.hk/-helena 6. Graph Algorithms-2CS3381 Des & Anal of Alg (2001-2002 SemA) City Univ of HK / Dept of CS / Helena Wong http://www.cs.cityu.edu.hk/~helena 6. Graph Algorithms - 2 Graph Algorithms Coming up Useful data structures: • Heaps & Priority Queues (Chap 6) • Disjoint Sets (Chap 21) Graph Algorithms • Elementary Graph Algorithms (Chap 22) Graph Representations • Breadth-first search • Depth-first search • Topological sort • Minimum Spanning Trees (Chap 23) Kruskal’s algorithm, Prim’s algorithm • Single-Source Shortest Paths (Chap 24) Bellman-Ford Algorithm • Algorithm for Directed Acyclic Graph • Dijkstra’s Algorithm • All-Pairs Shortest Paths (Chap 25) Shortest Paths by repeated squaring • Floyd-Warshall Alg • Johnson’s Alg