# UMD CMSC 420 - Minimum Spanning Trees (35 pages)

Previewing pages*1, 2, 16, 17, 18, 34, 35*of 35 page document

**View the full content.**## Minimum Spanning Trees

Previewing pages
*1, 2, 16, 17, 18, 34, 35*
of
actual document.

**View the full content.**View Full Document

## Minimum Spanning Trees

0 0 65 views

- Pages:
- 35
- School:
- University of Maryland, College Park
- Course:
- Cmsc 420 - Data Structures

**Unformatted text preview:**

Minimum Spanning Trees CMSC 420 Lecture 11 Following Dave Mount s lecture in his lecture notes Skew Heaps Self adjusting version of leftist heaps Difference Don t store npl or any other auxiliary information at the nodes always swap the left right subtrees at each step of meld old rightmost path becomes new leftmost path Can show beyond the scope of this class that a series of m insert findmin meld operations take O m log n time like splay trees each operation takes O log n amortized time Decrease Key decreasekey pointer d subtract d from the key at the node pointed to by pointer How would you implement this to run in O log n time 1 Subtract d from the key pointer 2 sift up Handling Moving References Problem Suppose you have a heap and are also keeping pointers to objects stored in the heap to use for delete decrease key When you sift up nodes are going to move around and the pointers will become invalid How would you solve this 3 H 21 14 23 p1 8 10 17 26 p2 Handling Moving References Problem Suppose you have a heap and are also keeping pointers to objects stored in the heap to use for delete decrease key When you sift up nodes are going to move around and the pointers will become invalid How would you solve this 3 H 21 14 23 p1 8 10 17 26 p2 Handling Moving References key 3 loc ptr key 8 loc ptr key 17 loc ptr 3 H 8 10 21 14 23 p1 17 26 p2 Spanning Trees Given a graph G V E A spanning tree is a connected acyclic subset of edges that connects together all the vertices To connect all vertices with the fewest number of edges it never makes sense to include a cycle If graph is weighed by putting real numbers on each edge then we can look for a minimum cost spanning tree called the minimum spanning tree Example Spanning Trees Example Spanning Tree Example Spanning Tree Example Uses Cable routing connect houses with telephone or television cable Circuit Wiring minimum amount of solder or heat Minimum Spanning Trees 10 4 8 7 6 9 8 Cost is 33 5 2 9 1 2 Minimum Spanning Trees 10 4 8 7 6 9 8 Cost is 22 5 2 9 1 2 Minimum Spanning Trees There may be several MSTs 10 4 8 7 6 9 8 Cost is 22 5 2 9 1 2 Steiner Trees A Steiner tree is a tree that connects a given subset of vertices called terminal nodes Steiner points Terminals Example Euclidian MST Often vertices are embedded in plane and distance is Euclidian distance Example of metric MST 1 1 1 1 Cost of MST 3 Example Metric Steiner Tree 1 Cost 2 2 2 83 1 Example of metric Steiner Tree 1 If allowed to add points then cost can be reduced Which is computationally harder MST G Steiner G V Steiner tree where every vertex is a terminal is the same as MST For which do you think there are faster algorithms A MST B Steiner C Trick question D Hard question MST is fast MST is fast best is nearly linear How do we find the minimum spanning tree But no known fast algorithms for Steiner tree NPhard Cuts A cut of a graph is a partition of its vertices into two groups Sometimes we refer to the edges that go from one group to another as the cut A edge u v with u in S and v in V S crosses the cut S V S Viable Sets Safe Edges An set of edges is viable if it can be extended to form a MST An edge is safe if adding it to a viable set creates another viable set If we can start with an empty edge set A which is viable and successively add n 1 safe edges we ll end up with a MST Which edges are safe and how do we find them quickly Respecting Cuts V S u S A cut respects a set of edges A if no edge in A crosses the cut Respecting Cuts V S u S If T is the set of tree edges added so far and S V S is an T respecting cut So these are candidates to add to the growing MST then edges that cross S V S can be added to the tree without creating a cycle Prim s Algorithm Idea V S u S S the set of nodes already in the tree S defines a cut of the graph Prim s Algorithm Idea V S u S Repeat Add a node u to S from V S S S u How do you choose u Prim s Algorithm Idea V S u S Greedy idea Choose the edge with the smallest weight that cross the T respecting cut Greedy Algorithms Repeatedly selected a locally optimal choice Never undo a choice you ve already made How do you know this will result in the minimum cost spanning tree Free Tree Facts Tree of n nodes has n 1 edges There is a unique path between any pair of nodes if there were two paths then there would be a cycle if there were 0 paths wouldn t be connected Adding any additional edges creates a cycle MST Lemma Thm If T is a viable subset of E and S V S is a T respecting cut then the minimum weight edge that crosses S V S is safe Proof Suppose u v is the minimum weight edge and it is NOT safe Then it is in NO MST So let Q be a MST Add u v to Q Q a subgraph with a cycle At least two edges of the cycle in Q cross S V S why V S v u S y x x y is not in T because the cut was T respecting So remove x y from Q to get an NEW spanning tree Q cost Q cost Q w x y w u v w u v w x y because u v was the minimum weight edge Therefore Q is a lower cost spanning tree than Q But Q was a MST Contradiction Prim s Algorithm The heap At every step we re adding the minimum weight edge that crosses the cut Is there a way to find this minimum edge quickly A heap What do we store in the heap Storing edges is problematic If we put edges into the heap we have to do complicated updates when we add a node to S V Vu S u S Better idea Store NODES in heap Heap stores nodes that are not yet in the spanning tree aka nodes in V S key u weight of lowest cost edge going from current T to u key u INFINITY if there is no edge from T to u Vu S def MST Prim G root initialize for u in Vertices G u key infinity u …

View Full Document