Robert Sedgewick and Kevin Wayne • Copyright © 2005 • http://www.Princeton.EDU/~cos226Minimum Spanning TreeReference: Chapter 20, Algorithms in Java, 3rd Edition, Robert Sedgewick.2Minimum Spanning TreeMST. Given connected graph G with positive edge weights, find a minweight set of edges that connects all of the vertices.231021 1424 16 4189711 8G563Minimum Spanning TreeMST. Given connected graph G with positive edge weights, find a minweight set of edges that connects all of the vertices.Theorem. [Cayley 1889] There are VV-2 spanning trees on the completegraph on V vertices.can't solve by brute force231021 1424 16 4189711 8cost(T) = 50564MST OriginOtakar Boruvka (1926).! Electrical Power Company of Western Moravia in Brno.! Most economical construction of electrical power network.! Concrete engineering problem is now a cornerstone problem incombinatorial optimization.Otakar Boruvka5ApplicationsMST is fundamental problem with diverse applications.! Network design.– telephone, electrical, hydraulic, TV cable, computer, road! Approximation algorithms for NP-hard problems.– traveling salesperson problem, Steiner tree! Indirect applications.– max bottleneck paths– LDPC codes for error correction– image registration with Renyi entropy– learning salient features for real-time face verification– reducing data storage in sequencing amino acids in a protein– model locality of particle interactions in turbulent fluid flows– autoconfig protocol for Ethernet bridging to avoid cycles in a network! Cluster analysis.6Medical Image ProcessingMST describes arrangement of nuclei in the epithelium for cancer researchhttp://www.bccrc.ca/ci/ta01_archlevel.html8Two Greedy AlgorithmsKruskal's algorithm. Consider edges in ascending order of cost.Add the next edge to T unless doing so would create a cycle.Prim's algorithm. Start with any vertex s and greedily grow a tree Tfrom s. At each step, add the cheapest edge to T that has exactly oneendpoint in T.Theorem. Both greedy algorithms compute an MST.Greed is good. Greed is right. Greed works. Greedclarifies, cuts through, and captures the essence ofthe evolutionary spirit." - Gordon GeckoRobert Sedgewick and Kevin Wayne • Copyright © 2005 • http://www.Princeton.EDU/~cos226Weighted Graphs10Weighted Graph Interfacefor (int v = 0; v < G.V(); v++) { for (Edge e : G.adj(v)) { int w = e.other(v); // edge v-w }}iterate through all edges (once in each direction)Return TypeWeightedGraph(int V)Method Actioncreate empty graphvoid insert(Edge e)add edge eIterable<Edge> adj(int v)return iterator over edges incident to vint V()return number of verticesString toString()return string representation11Edge Data Typepublic class Edge implements Comparable<Edge> { public final int v, int w; public final double weight; public Edge(int v, int w, double weight) { this.v = v; this.w = w; this.weight = weight; } public int other(int vertex) { if (vertex == v) return w; else return v; } public int compareTo(Edge f) { Edge e = this; if (e.weight < f.weight) return -1; else if (e.weight > f.weight) return +1; else if (e.weight > f.weight) return 0; }}12public class WeightedGraph { private int V; // # vertices private Sequence<Edge>[] adj; // adjacency lists public Graph(int V) { this.V = V; adj = new (Sequence<Edge>[]) Sequence[V]; for (int v = 0; v < V; v++) adj[v] = new Sequence<Edge>(); } public void insert(Edge e) { int v = e.v, w = e.w; adj[v].add(e); adj[w].add(e); } public Iterable<Edge> adj(int v) { return adj[v]; }}Weighted Graph: Java ImplementationIdentical to Graph.java but use Edge adjacency lists instead of int.Robert Sedgewick and Kevin Wayne • Copyright © 2005 • http://www.Princeton.EDU/~cos226MST Structure14Spanning TreeMST. Given connected graph G with positive edge weights, find a minweight set of edges that connects all of the vertices.Def. A spanning tree of a graph G is a subgraph T that is connectedand acyclic.Property. MST of G is always a spanning tree.15Greedy AlgorithmsSimplifying assumption. All edge costs ce are distinct.Cycle property. Let C be any cycle, and let f be the max cost edgebelonging to C. Then the MST does not contain f.Cut property. Let S be any subset of vertices, and let e be the mincost edge with exactly one endpoint in S. Then the MST contains e.fCSe is in the MSTef is not in the MST16Cut PropertySimplifying assumption. All edge costs ce are distinct.Cut property. Let S be any subset of vertices, and let e be the min costedge with exactly one endpoint in S. Then the MST T* contains e.Pf. [by contradiction]! Suppose e does not belong to T*. Let's see what happens.! Adding e to T* creates a (unique) cycle C in T*.! Some other edge in C, say f, has exactly one endpoint in S.! T = T* ! { e } " { f } is also a spanning tree.! Since ce < cf, cost(T) < cost(T*).! This is a contradiction. !f T*eS17Cycle PropertySimplifying assumption. All edge costs ce are distinct.Cycle property. Let C be any cycle in G, and let f be the max cost edgebelonging to C. Then the MST T* does not contain f.Pf. [by contradiction]! Suppose f belongs to T*. Let's see what happens.! Deleting f from T* disconnects T*. Let S be one side of the cut.! Some other edge in C, say e, has exactly one endpoint in S.! T = T* ! { e } " { f } is also a spanning tree.! Since ce < cf, cost(T) < cost(T*).! This is a contradiction. !f T*eSRobert Sedgewick and Kevin Wayne • Copyright © 2005 • http://www.Princeton.EDU/~cos226Kruskal's Algorithm19Kruskal's algorithm. [Kruskal 1956] Consider edges in ascending orderof cost. Add the next edge to T unless doing so would create a cycle.Kruskal's Algorithm: Example3-5 1-7 6-70-2 0-7 0-1 3-4 4-5 4-720Kruskal's Algorithm: Example25%50%75%100%21CeKruskal's Algorithm: Proof of CorrectnessTheorem. Kruskal's algorithm computes the MST.Pf (case 1). If adding e to T creates a cycle C, then e is the max weightedge in C, so the cycle property asserts that e is not in the MST.22wveSKruskal's Algorithm: Proof of CorrectnessTheorem. Kruskal's algorithm computes the MST.Pf (case 2). If adding e = (v, w) to T does not create a cycle, thene is the min weight edge with exactly one endpoint in S, so thecut property asserts that e is in the MST. !set of vertices inv's connected component23Kruskal's Algorithm: ImplementationQ. How to check if adding an edge to T would create a cycle?A1. Naïve
View Full Document
Unlocking...