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 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
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
Heaps Priority Queues Building a heap BUILD-MAX-HEAP(Input_numbers) 1 Copy Input numbers to a heap 3 MAX-HEAPIFY(A O(n) note that n/2 the elements are leaf nodes Casual illustration for a Com plete-binary tree A complete- binary tree of height h has h+1 levels: 0, 1, 2, 3,h The levels have 20, 21, 22, 23, .2h elements respectively Then maximum total no of float down" carried out by maX-HeaPify sum of maximum no of"float down"of all non-leaf nodes(levels h-1, h-2, ..O =1X2h1+2x2h2+3X2h3+4x2h4+hX20 =2(1/2+214+38+416.) [note: 2+1=n+1, thus 2 =0.5*(n+1) 0.5(n+1)(12+24+3/8+4/16.)[note:12+2/4+3/8+4/16.<2] 0.5(+1)*2=(n+1) o(n) CS3381 Des Anal of Alg(2001-2002 SemA) Continue City Univ of HK /Dept of CS Helena Wong http://www.cs.cityu.edu.hk/-helena 6. Graph Algorithms-6
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 - 6 Heaps & Priority Queues BUILD-MAX-HEAP(Input_numbers) 1 Copy Input_numbers to a heap 2 For i = n/2 down to 1 /*all non-leaf nodes */ 3 MAX-HEAPIFY(A,i) Building a heap: 1 2 3 4 5 6 7 8 9 10 .. .. 11 14 15 Note that n/2the elements are leaf nodes 1 2 3 4 5 6 7 8 9 10 Casual illustration for a Complete-binary tree: A complete-binary tree of height h has h+1 levels: 0,1,2,3,.. h. The levels have 20 ,21 ,22 ,23 ,…2h elements respectively. Then, maximum total no. of “float down” carried out by MAX-HEAPIFY = sum of maximum no. of “float down” of all non-leaf nodes (levels h-1, h-2, .. 0) = 1 x 2h-1 + 2 x 2h-2 + 3 x 2h-3 + 4 x 2h-4 + .. h x 20 = 2h (1/2 + 2/4 + 3/8 + 4/16…) [note: 2h+1 = n+1, thus 2h=0.5*(n+1)] = 0.5(n+1) (1/2 + 2/4 + 3/8 + 4/16…) [note: 1/2 + 2/4 + 3/8 + 4/16.. <2] < 0.5(n+1) * 2 = (n+1) = O(n) O(n) Show Summation Continue
lllustration:1/2+214+3/{8+4/16..<2 12 =0.5 Return 1/2+24 1/2+24+3/8 1375 1/2+24+3/8+4/16 =1625 1/2+24+3/8+4/16+5/32 =178125 1/2+24+3/8+416+5/32+6/64 =1875 1/2+24+318+4/16+532+6/64+7/128 =19296875 1/2+24+318+4/16+532+6/64+7/128+8/256 =19609375 1/2+24+318+4/16+532+6/64+7/128+8/256+9/512 1978515625 1/2+24+38+4/16+5/32+664+7/128+8/256+9512+10/1024 =198828125 1/2+24+3/8+416+5/32+6/64+7/128+8/256+9/512+10/1024+112048=1993652344 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-7
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 - 7 Illustration: 1/2 + 2/4 + 3/8 + 4/16.. <2 1/2 = 0.5 1/2+2/4 = 1 1/2+2/4+3/8 = 1.375 1/2+2/4+3/8+4/16 = 1.625 1/2+2/4+3/8+4/16+5/32 = 1.78125 1/2+2/4+3/8+4/16+5/32+6/64 = 1.875 1/2+2/4+3/8+4/16+5/32+6/64+7/128 = 1.9296875 1/2+2/4+3/8+4/16+5/32+6/64+7/128+8/256 = 1.9609375 1/2+2/4+3/8+4/16+5/32+6/64+7/128+8/256+9/512 = 1.978515625 1/2+2/4+3/8+4/16+5/32+6/64+7/128+8/256+9/512+10/1024 = 1.98828125 1/2+2/4+3/8+4/16+5/32+6/64+7/128+8/256+9/512+10/1024+11/2048 = 1.993652344 Return
Heaps Priority Queues Priority queue 9 Is a data structure for maintaining a set of elements each associated with a key e Maximum priority queue supports the following operations INSERT(S, x) Insert element x into the set s MAXIMUM(S Return the 'largest element EXTRACT-MAX(S)-Remove and return the 'largest element INCREASE-KEY(S, x,v)-Increase x's key to a new value, V We can implement priority queues based on a heap structure 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-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 - 8 Heaps & Priority Queues Priority queue Is a data structure for maintaining a set of elements each associated with a key. Maximum priority queue supports the following operations: INSERT(S,x) - Insert element x into the set S MAXIMUM(S) - Return the ‘largest’ element EXTRACT-MAX(S) - Remove and return the ‘largest’ element INCREASE-KEY(S,x,v) - Increase x’s key to a new value, v We can implement priority queues based on a heap structure
Heaps Priority Queues MAXIMUM(A) 1 return A[1] ⊙(1) ②2④① HEAP-EXTRACT-MAX(A) o( 16 234567 ⑦ ⑦(9)(③3) ②④④ Step 1. save the value of the root that is to be returned Step 2. Move the last value to the root node Step 3. MAX-HEAPIFY(A, 1/ the root node*) 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-9
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 - 9 HEAP-EXTRACT-MAX(A) 1 2 3 4 5 6 7 Step 1. Save the value of the root that is to be returned. Step 2. Move the last value to the root node. Step 3. MAX-HEAPIFY(A,1/*the root node*/). Heaps & Priority Queues MAXIMUM(A) 1 return A[1] 16 14 10 8 7 9 3 2 4 1 14 10 8 7 9 3 2 4 1 16 1 14 10 8 7 9 3 2 4 14 8 10 4 7 9 3 2 1 (1) O(lg n)
Heaps Priority Queues HEAP-INCREASE-KEY(A, v) o(lg n) 40 16 3 Increase 58⑦⑨③ 0⑩ 0④④ 8④④ ⑧④④ Keep on exchanging with parent until parent is greater than the current node o(g n) MAX-HEAP-INSERT(A, key) 1n=n+1 ⑩ 2A]=-0 3 HEAP-INCREASE-KEY(A, n, key②④④ ②④⑩ 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-10
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 - 10 Heaps & Priority Queues HEAP-INCREASE-KEY(A,i,v) 1 2 3 4 5 6 MAX-HEAP-INSERT(A,key) 1 n = n+1 2 A[n]= - 3 HEAP-INCREASE-KEY(A,n,key) 16 14 10 8 7 9 3 2 4 1 Increase to 15 16 14 10 8 7 9 3 15 4 1 16 14 10 15 7 9 3 8 4 1 16 15 10 14 7 9 3 8 4 1 Keep on exchanging with parent until parent is greater than the current node. O(lg n) 16 14 10 8 7 9 3 2 4 1 - 16 14 10 8 7 9 3 2 4 115 … O(lg n)