DOC PREVIEW
BU CS 333 - Minimum Spanning Tree Algorithms

This preview shows page 1-2-3-23-24-25-26-46-47-48 out of 48 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 48 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Minimum Spanning Tree AlgorithmsWhat is A Spanning Tree?Minimal Spanning Tree.Example of a Problem that Translates into a MSTGreedy ChoiceNotationThe Prim algorithm Main IdeaImplementation IssuesSlide 9Slide 10Slide 11Slide 12Prim’s AlgorithmPrim’s Algorithm InitializationBuilding the MSTTime AnalysisSlide 17Prim - extended Heap After InitializationPrim - extended Heap Build tree - after PQ.extractMinUpdate B adjacent to AUpdate C adjacent to ABuild tree - after PQ.extractMinUpdate C adjacent to BSlide 24Prim - unsorted list After InitializationSlide 26Update B, C adjacent to ASlide 28Update B adjacent to CSlide 30Slide 31Slide 32Lemma 1Outline of Proof of Correctness of Lemma 1The Promising Set of Edges Selected by PrimSince T' is a spanning tree, it is connected. Adding the edge, e, creates a cycle.Slide 37Slide 38Theorem : Prim's Algorithm always produces a minimum spanning tree.Slide 40Kruskal's Algorithm: Main IdeaKruskal's Algorithm:Kruskal - Disjoint set After InitializationKruskal - add minimum weight edge if feasibleSlide 45Slide 46Slide 47Kruskal's Algorithm: Time AnalysisMinimum Spanning Tree AlgorithmsPrim’s AlgorithmKruskal’s AlgorithmRuntime AnalysisCorrectness ProofsCopyright 1999 by Cutler/HeadGreedy/Prims 2What is A Spanning Tree?uvbacdef•A spanning tree for an undirected graph G=(V,E) is a subgraph of G that is a tree and contains all the vertices of G •Can a graph have more than one spanning tree?•Can an unconnected graph have a spanning tree?Copyright 1999 by Cutler/HeadGreedy/Prims 3Minimal Spanning Tree.4432915810143uvbacdefMst T: w( T )=(u,v)  T w(u,v ) is minimized•The weight of a subgraph is the sum of the weights of it edges.•A minimum spanning tree for a weighted graph is a spanning tree with minimum weight.•Can a graph have more then one minimum spanning tree?Copyright 1999 by Cutler/HeadGreedy/Prims 4Example of a Problem that Translates into a MSTThe Problem•Several pins of an electronic circuit must be connected using the least amount of wire.Modeling the Problem •The graph is a complete, undirected graph G = ( V, E ,W ), where V is the set of pins, E is the set of all possible interconnections between the pairs of pins and w(e) is the length of the wire needed to connect the pair of vertices.•Find a minimum spanning tree.Copyright 1999 by Cutler/HeadGreedy/Prims 5Greedy ChoiceWe will show two ways to build a minimum spanning tree.•A MST can be grown from the current spanning tree by adding the nearest vertex and the edge connecting the nearest vertex to the MST. (Prim's algorithm)•A MST can be grown from a forest of spanning trees by adding the smallest edge connecting two spanning trees. (Kruskal's algorithm)Copyright 1999 by Cutler/HeadGreedy/Prims 6Notation•Tree-vertices: in the tree constructed so far•Non-tree vertices: rest of verticesPrim’s Selection rule•Select the minimum weight edge between a tree-node and a non-tree node and add to the treeCopyright 1999 by Cutler/HeadGreedy/Prims 7The Prim algorithm Main IdeaSelect a vertex to be a tree-nodewhi le (there are non-tree vertices) { if there is no edge connecting a tree node with a non-tree node return “no spanning tree”select an edge of minimum weight between a tree node and a non-tree nodeadd the selected edge and its new vertex to the tree}return tree645215810143uvbacdfCopyright 1999 by Cutler/HeadGreedy/Prims 8Implementation Issues•How is the graph implemented?–Assume that we just added node u to the tree.–The distance of the nodes adjacent to u to the tree may now be decreased.–There must be fast access to all the adjacent vertices.–So using adjacency lists seems better •How should the set of non-tree vertices be represented?–The operations are:•build set•delete node closest to tree•decrease the distance of a non-tree node from the tree•check whether a node is a non- tree nodeCopyright 1999 by Cutler/HeadGreedy/Prims 9Implementation Issues•How should the set of non-tree vertices be represented?–A priority queue PQ may be used with the priority D[v] equal to the minimum distance of each non-tree vertex v to the tree.–Each item in PQ contains: D[v], the vertex v, and the shortest distance edge (v, u) where u is a tree node•This means:–build a PQ of non-tree nodes with initial values - •fast build heap O (V ) •building an unsorted list O(V)•building a sorted list O(V) (special case)Copyright 1999 by Cutler/HeadGreedy/Prims 10Implementation Issues–delete node closest to tree (extractMin)•O(lg V ) if heap and •O(V) if unsorted list •O(1) sorted list–decrease the distance of a non-tree node to the tree–We need to find the location i of node v in the priority queue and then execute (decreasePriorityValue(i, p)) where p is the new priority –decreasePriorityValue(i, p)•O(lg V) for heap,•O(1) for unsorted list •O(V ) for sorted list (too slow)Copyright 1999 by Cutler/HeadGreedy/Prims 11Implementation Issues•What is the location i of node v in a priority queue?–Find in Heaps, and sorted lists O(n)–Unsorted – if the nodes are numbered 1 to n and we use an array where node v is the v item in the array O(1)Extended heap–We will use extended heaps that contain a “handle” to the location of each node in the heap.–When a node is not in PQ the “handle” will indicate that this is the case–This means that we can access a node in the extended heap in O(1), and check v  PQ in O(1)–Note that the “handle” must be updated whenever a heap operation is appliedCopyright 1999 by Cutler/HeadGreedy/Prims 12Implementation Issues2. Unsorted list–Array implementation where node v can be accesses as PQ[v] in O(1), and the value of PQ[v] indicates when the node is not in PQ.Copyright 1999 by Cutler/HeadGreedy/Prims 13Lines 1-5 initialize the priority queue PQ to contain all Vertices. Ds for all vertices except r, are set to infinity. r is the starting vertex of the TThe T so far is emptyAdd closest vertex and edge to current TGet all adjacent vertices v of u,update D of each non-tree vertex adjacent to uStore the current minimum weight edge, and updated distance in the priority queuePrim’s Algorithm 1. for each u V2. do D [u ]  3. D[ r ]  0 4. PQ make-heap(D,V, {})//No edges 5. T  6.7. while PQ   do 8. (u,e )  PQ.extractMin() 9. add (u,e) to T10. for each v  Adjacent (u ) // execute relaxation 11. do if v PQ && w(


View Full Document

BU CS 333 - Minimum Spanning Tree Algorithms

Download Minimum Spanning Tree Algorithms
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 Tree Algorithms 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 Tree Algorithms 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?