Minimum Spanning Trees 2704 BOS 867 849 ORD 1846 LAX 1391 1464 1235 JFK PVD 144 1258 184 802 SFO 337 740 621 187 BWI 1090 DFW 946 1121 MIA 2342 2010 Goodrich Tamassia Minimum Spanning Trees 1 Minimum Spanning Trees Spanning subgraph Spanning tree Spanning subgraph that is itself a free tree Minimum spanning tree MST Spanning tree of a weighted graph with minimum total edge weight Applications ORD Subgraph of a graph G containing all the vertices of G Communications networks Transportation networks 2010 Goodrich Tamassia 10 1 DEN PIT 6 7 9 STL 4 8 DFW Minimum Spanning Trees 3 DCA 3 2 ATL 2 Cycle Property Cycle Property f Let T be a minimum spanning tree of a weighted graph G Let e be an edge of G that is not in T and C let be the cycle formed by e with T For every edge f of C weight f weight e Proof By contradiction If weight f weight e we can get a spanning tree of smaller weight by replacing e with f 4 C 2010 Goodrich Tamassia 8 2 9 6 3 e 8 7 7 Replacing f with e yields a better spanning tree f 2 Minimum Spanning Trees 6 8 4 C 9 3 8 e 7 7 3 Partition Property U f Partition Property Consider a partition of the vertices of G into subsets U and V Let e be an edge of minimum weight across the partition There is a minimum spanning tree of G containing edge e Proof Let T be an MST of G If T does not contain e consider the cycle C formed by e with T and let f be an edge of C across the partition By the cycle property weight f weight e Thus weight f weight e We obtain another MST by replacing f with e V 7 4 2010 Goodrich Tamassia 9 5 2 8 8 3 e 7 Replacing f with e yields another MST U 2 Minimum Spanning Trees f V 7 4 9 5 8 8 3 e 7 4 Algorithm Characteristics Both Prim s and Kruskal s Algorithms work with undirected graphs Both work with weighted and unweighted graphs but are more interesting when edges are weighted Both are greedy algorithms that produce optimal solutions Kruskal s Algorithm Maintain a partition of the Algorithm KruskalMST G for each vertex v in G do vertices into clusters Create a cluster consisting of v Initially single vertex let Q be a priority queue clusters Insert all edges into Q Keep an MST for each T cluster T is the union of the MSTs of the clusters Merge closest clusters while T has fewer than n 1 edges do and their MSTs e Q removeMin getValue A priority queue stores the u v G endVertices e edges outside clusters A getCluster u Key weight B getCluster v Element edge if A B then At the end of the Add edge e to T algorithm mergeClusters A B One cluster and one MST return T 2010 Goodrich Tamassia Minimum Spanning Trees 6 Example 8 B 1 A G 5 9 C 11 7 E 4 6 F 3 D H 2 10 2010 Goodrich Tamassia Campus Tour 7 Example 8 B 5 1 E 4 6 F 3 C 11 H D 2 10 G 8 B A 9 7 A 1 G 5 9 C 11 7 E 4 6 F 3 D H 2 10 2010 Goodrich Tamassia Campus Tour 8 Example 8 B 5 1 E 6 F 3 C 11 H D 2 A 5 9 C 11 7 E 4 6 F 3 D H 2 10 G 8 5 1 G 8 B 4 10 B A 9 7 A 1 G 9 C 11 7 E 4 6 F 3 D H 2 10 2010 Goodrich Tamassia 10 Campus Tour 9 Example 8 B 5 1 E 6 F 3 C 11 H D 2 C 11 7 A 9 C 11 7 E 6 F 3 D H 2 A 10 2010 Goodrich Tamassia 1 Campus Tour E 6 F 3 H D 2 G 8 B 4 4 10 G 8 5 9 5 1 G 8 B 4 10 B A 9 7 A 1 G 5 9 C 11 7 E 4 6 F 3 D H 2 10 10 Example contd B 1 A G 8 5 9 C 11 7 E 4 6 F 3 D H 2 10 2010 Goodrich Tamassia Campus Tour 11 Example contd B 5 1 E 4 6 F 3 C 11 H D 2 10 G 8 B A 9 7 A 1 G 8 5 9 C 11 7 E 4 6 F 3 D H 2 10 2010 Goodrich Tamassia Campus Tour 12 Example contd B 5 1 G 8 9 6 F 3 C 11 7 A E H D 8 B 4 1 2 A 5 9 C 11 7 E 4 6 F 3 D H 2 10 1 A 5 9 C 11 7 E tw 4 6 F 3 D o G 8 B st e ps 10 G H 2 10 2010 Goodrich Tamassia Campus Tour 13 Example contd B 5 1 G 8 9 6 F 3 C 11 7 A E H D 8 B 4 2 C 11 7 A 4 E 6 H D A 5 9 C 11 7 E 10 st e 6 F 3 D o 4 H 2010 Goodrich Tamassia 1 A Campus Tour G 8 B 2 10 2 four steps tw 8 B 1 G F 3 ps 10 9 5 1 G 5 9 C 11 7 E 4 6 F 3 D H 2 10 14 Data Structure for Kruskal s Algorithm The algorithm maintains a forest of trees A priority queue extracts the edges by increasing weight An edge is accepted it if connects distinct trees We need a data structure that maintains a partition i e a collection of disjoint sets with operations makeSet u create a set consisting of u find u return the set storing u union A B replace sets A and B with their union 2010 Goodrich Tamassia Minimum Spanning Trees 15 Kruskal s Algorithm Two steps Sort edges by increasing edge weight Select the first V 1 edges that do not generate a cycle Walk Through F 10 A 4 3 6 B 4 H C 4 8 5 Consider an undirected weight graph 3 D 4 1 2 3 G 3 E F 10 A 4 3 6 B 4 H C 4 8 5 Sort the edges by increasing edge weight 3 D 4 1 2 3 G 3 E edge dv edge dv D E 1 B E 4 D G 2 B F 4 E G 3 B H 4 C D 3 A H 5 G H 3 D F 6 C F 3 A B 8 B C 4 A F 10 Select first V 1 edges which do not generate a cycle F 10 A 3 …
View Full Document
Unlocking...