Graph algorithms 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-1
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 - 1 Graph Algorithms
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-2
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 - 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
Heaps Priority Queues Complete The(binary)heap data structure is binary tree an array object hat can be viewed as a nearly complete binary tree 1234567 16141087932 14 Parent(=Li2」 3 All leaves Left(o 891 have the Right( 21+1 2④4① same depth All internal A max-heap: child<= parent nodes have 2 children A min-heap: child > parent 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-3
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 - 3 Heaps & Priority Queues The (binary) heap data structure is: • All leaves have the same depth • All internal nodes have 2 children Complete binary tree: 16 14 10 8 7 9 3 2 4 1 16 14 10 8 7 9 3 2 4 1 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 an array object that can be viewed as a nearly complete binary tree Parent(i) = i/2 Left(i) = 2i Right(i) = 2i+1 A max-heap: child <= parent A min-heap: child >= parent
Heaps Priority Queues MAX-HEAPIFY(A, i The binary trees rooted at LEFT( and RIGHT( are max-heaps 234 But A[] may be smaller than its children MAX-HEAPlFY is to"float down"[]to o(height of node i) make the subtree rooted at A[i] a max-heap. =Olg n) 9)(3 ⑦9(3 8 9)(3 2)(8( 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-4
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 - 4 Heaps & Priority Queues MAX-HEAPIFY(A,i) 1 2 3 4 .. The binary trees rooted at LEFT(i) and RIGHT(i) are max-heaps But A[i] may be smaller than its children. MAX-HEAPIFY is to “float down” A[i] to make the subtree rooted at A[i] a max-heap. 16 4 10 14 7 9 3 2 8 1 1 i=2 3 4 5 6 7 8 9 10 16 14 10 4 7 9 3 2 8 1 1 2 3 i=4 5 6 7 8 9 10 16 14 10 8 7 9 3 2 4 1 1 2 3 4 5 6 7 8 i=910 O(height of node i) = O(lg n)
Heaps Priority Queues Maximum No of elements Maximum no of elements a one-level tree(height=0) level 0 a 2-level tree(height=1): 3 level 1 2 level 2 a 3-level tree (height=2): 7 level 3 8{8 a 4-level tree(height=3 15 Therefore, for a heap containing n elements Maximum no of elements in level k =2k Height of tree =LIg n ]=O(lg n) Basic procedures: MAX-HEAPIFY o(g n) HEAP-EXTRACT-MAX O(g n) BUILD-MAX-HEAP O(n) HEAP-INCREASE-KEY O(g n) MAX-HEAP-INSERT O(g n) HEAP-MAXIMUM o(g n) 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-5
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 - 5 Heaps & Priority Queues Basic procedures: MAX-HEAPIFY O(lg n) BUILD-MAX-HEAP O(n) MAX-HEAP-INSERT O(lg n) Maximum No. of elements Maximum No. of elements Therefore, for a heap containing n elements : a one-level tree (height=0): 1 1 2 3 4 5 6 7 8 9 10 Maximum no. of elements in level k = 2 Height of tree = lg n = (lg n) k HEAP-EXTRACT-MAX O(lg n) HEAP-INCREASE-KEY O(lg n) HEAP-MAXIMUM O(lg n) a 2-level tree (height=1): 3 a 3-level tree (height=2): 7 a 4-level tree (height=3): 15 level 0: 1 level 1: 2 level 2: 4 level 3: 8