Lecture 8 Greedy Approach Minimum spanning tree How to design greedy algorithms
• Minimum spanning tree • How to design greedy algorithms Lecture 8 Greedy Approach
Roadmap Minimum spanning tree How to design greedy algorithms a Change-making problem a Activity selection problem n Huffman code a Knapsack problem
Roadmap • Minimum spanning tree • How to design greedy algorithms ‣ Change-making problem ‣ Activity selection problem ‣ Huffman code ‣ Knapsack problem
MST Given. Undirected graph G with positive edge weights (connected) Def. A spanning tree of G is a subgraph T that is connected and 5 16 10 10 not connected not acyclic
MST Given. Undirected graph G with positive edge weights (connected). Def. A spanning tree of G is a subgraph T that is connected and acyclic. not connected 23 10 21 14 24 16 4 18 9 7 11 8 5 6 23 10 21 14 24 16 4 18 9 7 11 8 5 6 not acyclic
Minimum spanning tree Problem: Min Spanning Input: A connected undirected graphG=(V, E)in thich each edge has a weighted lenath Output: A spanning tree of G that has minimum cost
Minimum spanning tree Problem: MinSpanning Input: A connected undirected graph G = (V , E ) in which each edge has a weighted length Output: A spanning tree of G that has minimum cost a b h c i d e g f 4 2 7 4 10 9 8 11 8 7 1 2 6 a 14 b h c i d e g f 4 2 7 4 10 9 8 11 8 7 1 2 6 14
Cut property Definition: Cut A cut (S, T s a partition of the vertex set v into two subsets s and t heorem(Cut property)Given any cut, the crossing edge of min weight is in some MST
Cut property a b h c i d e g f 4 2 7 4 10 9 8 11 8 7 1 2 6 14 Definition: Cut A cut {S,T} is a partition of the vertex set V into two subsets S and T. Theorem (Cut property)Given any cut, the crossing edge of min weight is in some MST
Correctness Theorem(GeneralMSTAlgorithm) Let a be a subset of e that is included in some mst for g let V, S-V) be any cut of G that respects A, and let(u, v) be a lightest edge crossing V,S-V. Then, auf(u, v)) is included in some MST. Theorem Kruskal algorithm and Prim algorithm correctly find a minimum cost spanning tree
Correctness Theorem Kruskal algorithm and Prim algorithm correctly find a minimum cost spanning tree
Kruskal algorithm (h,g),(ci), (@, f), (a, b), (cf), (c, d), (ig),(ih),(b,c), (a, h ), d, e),(e, (b
Kruskal algorithm a b h c i d e g f 4 2 7 4 10 9 8 11 8 7 1 2 6 14 (h,g), (c,i), (g,f), (a,b), (c,f), (c,d), (i,g), (i,h), (b,c), (a,h), (d,e), (e,f), (b,h)
Kruskal algorithm Algorithm 8.3 Kruskal Input: A weighted connected undirected graph G=(V, E)with n vertIces Output: The set of the edges T of a minimum cost spanning tree fo g 1. Sort the edges in E by nondecreasing weigh 2. for each vertex v E V do Makeset((v)) end for 3.T= 4. while T<n-1 5. Let(x,y) be the next edge in E 6. if Find(x)*Find(y)then 7. Add(x, y) to T 8. Union(x, y) end if (mlog 10. end while
Kruskal algorithm
Prim algorithm
Prim algorithm a h c i d e g f 2 7 4 10 9 8 11 8 7 1 2 6 14 4
algorithm 8.4 Prim Input: A weighted connected undirected graph G=(V,E), where Output: The set of edges T of minimum cost spanning tree for G 1.T←(}:X←{1}:y←V1(1 2.foy←2ton 3. if y is ad acent to l then 4.My+1 6. C(y)+c(1, yl 6.esec←∞ 7. end if 8. end 9.forj←1ton-1 10. Let y be such that Cly is mInimum 11.T←TU{(y,My 12.X←Xuy 13.Y←Y(y 14. for each edge(y, w)such that wEY 15. if cly, w< Cothen 6789 cw←cb,wl (n) end if end for Heap: 0(mlogn) 20. end for
