Transcription of Kruskal’s Minimum Spanning Tree Algorithm & Union-Find ...
{{id}} {{{paragraph}}}
Example: marketing
Kruskal’s Minimum Spanning Tree Algorithm & Union-Find ...
Kruskal's Minimum Spanning tree Algorithm &. Union-Find Data Structures Slides by Carl Kingsford Jan. 21, 2013. Reading: AD Greedy Minimum Spanning tree rules All of these greedy rules work: 1. Starting with any root node, add the frontier edge with the smallest weight. (Prim's Algorithm ). 2. Add edges in increasing weight, skipping those whose addition would create a cycle. (Kruskal's Algorithm ). 3. Start with all edges, remove them in decreasing order of weight, skipping those whose removal would disconnect the graph. ( Reverse-Delete Algorithm ). Prim's Algorithm Prim's Algorithm : Starting with any root node, add the frontier edge with the smallest weight. Theorem. Prim's Algorithm produces a Minimum Spanning tree . v e r u S = set of nodes already in the tree when e is added Cycle Property Theorem (Cycle Property).
in any MST of G. Suppose the theorem is false. Let T be a MST that contains e. Deleting e from T partitions vertices into 2 sets: S (that contains u) and V S (that contains v). Cycle C must have some other edge f that goes from S and V S. Replacing e by f produces a lower cost tree, contradicting that T is an MST.
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: