MST-Kruskal( G, w ).ppt

UNC Chapel Hill Lin/Foskey/Manocha MST- Kruskal( G, w ) 1. A??// initially A is empty 2. for each vertex v ? V[G ] // line 2-3 takes O(V ) time 3. do Create-Set( v) // create set for each vertex 4. sort the edges of E by nondecreasing weight w 5. for each edge ( u,v)? E, in order by nondecreasing weight 6. do if Find-Set( u ) ? Find-Set( v ) // u&v on different trees 7. then A? A ?{(u,v)} 8. Union( u,v) 9. return A Total running time is O( E lg E ). UNC Chapel Hill Lin/Foskey/Manocha Analysis of Kruskal ? Lines 1-3 (initialization): O(V) ? Line 4 (sorting): O(E lgE) ? Lines 6-8 (set operations): O(E log E) ? Total: O(E log E) UNC Chapel Hill Lin/Foskey/Manocha Correctness of Kruskal ? Idea: Show that every edge added is a safe edge for A ? Assume ( u, v ) is next edge to be added to A. – Will not create a cycle ? Let A’ denote the tree of the forest A that contains vertex u . Consider the cut ( A’, V-A ’). – This cut respects A (why?) – and ( u, v ) is the light edge across the cut (why?) ? Thus, by the MST Lemma, ( u,v ) is safe. UNC Chapel Hill Lin/Foskey/Manocha Intuition behind Prim ’s Algorithm ? Consider the set of vertices S currently part of the tree, and plement ( V-S ). We have a cut of the graph and the current set of tree edges A is respected by this cut. ? Which edge should we add next? Light edge! UNC Chapel Hill Lin/Foskey/Manocha Basics of Prim ’ s Algorithm ? It works by adding leaves on at a time to the current tree. – Start with the root vertex r (it can be any vertex). At any time, the subset of edges A forms a single tree. S = vertices of A.– At each step, a light edge connecting a vertex in S to a vertex in V- S is added to the tree. – The tree grows until it spans all the vertices in V. ? Implementation Issues: – How to update the cut efficiently? – How to determine the light edge quickly? UNC