Unformatted text preview:

Minimum Spanning TreesCMSC 420: Lecture 11Following Dave Mount’s lecture in his lecture notes.Skew Heaps•Self-adjusting version of leftist heaps•Don’t store npl (or any other auxiliary information at the nodes)•Difference:-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•How would you implement this to run in O(log n) time?decreasekey(pointer, d): subtract d from the key at the node pointed to by pointer.1. Subtract d from the key @ pointer2. sift upHandling 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?81726231410213Hp1p2Handling 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?81726231410213Hp1p2Handling Moving References81726231410213Hp1p2key = 3loc = ptr key = 8loc = ptr key = 17loc = ptr ...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 TreesExample – Spanning TreeExample – Spanning TreeExample Uses•Cable routing: connect houses with telephone or television cable.•Circuit Wiring: minimum amount of solder or heat.Minimum Spanning Trees108 7912984625Cost is 33Minimum Spanning Trees108 7912984625Cost is 22Minimum Spanning Trees108 7912984625Cost is 22There may be several MSTsSteiner TreesTerminalsSteinerpoints•A Steiner tree is a tree that connects a given subset of vertices (called terminal nodes)Example – Euclidian MST111Often vertices are embedded in plane and distance is Euclidian distanceExample of metric MST1Cost of MST = 3Example Metric Steiner Tree111If allowed to add points, then cost can be reduced.Example of metric Steiner TreeCost = 2√2 = 2.83Which 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.•But no known fast algorithms for Steiner tree (NP-hard)•How do we find the minimum spanning tree?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 - SViable 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 CutsSV - SuA cut respects a set of edges A if no edge in Acrosses the cut.Respecting CutsSV - SuIf T is the set of tree edges added so far, and (S,V-S) is an T-respecting cutthen edges that cross (S,V-S) can be added to the tree without creating a cycle.So: these are candidates to add to the growing MSTPrim’s Algorithm: IdeaSV - SS = the set of nodes already in the tree;S defines a cut of the graph.uPrim’s Algorithm: IdeaSV - SS := S + {u}uAdd a node u to S from V-S.Repeat:How do you choose u?Prim’s Algorithm: IdeaSV - SGreedy idea: Choose the edge with the smallest weight that cross the T-respecting cut.uGreedy 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 LemmaThm. 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?]SV - Suvxy(x,y) is not in T because the cut was T-respectingSo: 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 QBut 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:SV - uSV uBetter 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.SV - udef MST_Prim(G, root): # initialize for u in Vertices(G): u.key = infinity u.intree = False u.parent = None # root has the smallest key (so extracted first) root.key = 0; # create a heap of the vertices not in the tree Q = Heap(Vertices(G)) # while there are vertices not in the tree while not Empty(Q): # find vertex that can be connected to S most cheaply u = Q.deletemin() # update its neighbors that are not in the tree for v in Neighbors(u): if not v.intree and w(u,v) < v.key: Q.decrease_key(v, v.key - w(u,v)) v.key = w(u,v) v.parent = u u.intree = TruePrim’s Running Time•Each time you add a vertex to the tree, you


View Full Document

UMD CMSC 420 - Minimum Spanning Trees

Download Minimum Spanning Trees
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Minimum Spanning Trees and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Minimum Spanning Trees 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?