Copyright © 2007 by Robert Sedgewick and Kevin Wayne.Minimum Spanning TreeReferences: Algorithms in Java (Part 5), Chapter 20Intro to Algs and Data Structures, Section 5.4•introduction•Weighted graph API•cycles and cuts•Kruskal’s algorithm•Prim’s algorithm•advanced algorithms•clustering 2introductionweighted graph APIcycles and cutsKruskal’s algorithmPrim’s algorithmadvanced algorithmsclustering3Minimum Spanning TreeMST. Given connected graph G with positive edge weights, find a min weight set of edges that connects all of the vertices.2310 21 1424 16 4189711 8G564Minimum Spanning TreeMST. Given connected graph G with positive edge weights, find a min weight set of edges that connects all of the vertices.Brute force: Try all possible spanning trees!problem 1: not so easy to implement!problem 2: far too many of them2310 21 1424 16 4189711 8cost(T) = 5056Ex: [Cayley, 1889]: VV-2 spanning trees on the complete graph on V vertices.5MST 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 in combinatorial optimization.Otakar Boruvka6ApplicationsMST 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.7Medical Image ProcessingMST describes arrangement of nuclei in the epithelium for cancer researchhttp://www.bccrc.ca/ci/ta01_archlevel.html8http://ginger.indstate.edu/ge/gfx9Two 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 T from s. At each step, add the cheapest edge to T that has exactlyone endpoint in T.Theorem. Both greedy algorithms compute an MST.Greed is good. Greed is right. Greed works. Greed clarifies, cuts through, and captures the essence of the evolutionary spirit." - Gordon Gecko 10introductionweighted graph APIcycles and cutsKruskal’s algorithmPrim’s algorithmadvanced algorithmsclustering11Weighted 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)create an empty graph with V verticesWeightedGraph(int V)public class WeightedGraph (graph data type)insert edge einsert(Edge e)voidreturn an iterator over edges incident to vadj(int v)Iterable<Edge>return the number of verticesV()intreturn a string representationtoString()String12Edge 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 either() { return v; } 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; }}Identical to Graph.java but use Edge adjacency lists instead of int.13public class WeightedGraph{ private int V; private Sequence<Edge>[] adj; public Graph(int V) { this.V = V; adj = (Sequence<Edge>[]) new 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 implementation 14introductionweighted graph APIcycles and cutsKruskal’s algorithmPrim’s algorithmadvanced algorithmsclustering15Spanning TreeMST. Given connected graph G with positive edge weights,find a min weight set of edges that connects all of the vertices.Def. A spanning tree of a graph G is a subgraph T that isconnected and acyclic.Property. MST of G is always a spanning tree.16Greedy AlgorithmsSimplifying assumption. All edge costs ce are distinct.Cycle property. Let C be any cycle, and let f be the max cost edge belonging to C. Then the MST does not contain f. Cut property. Let S be any subset of vertices, and let e be the min cost edge with exactly one endpoint in S. Then the MST contains e.f CSe is in the MSTef is not in the MST17Cycle PropertySimplifying assumption. All edge costs ce are distinct.Cycle property. Let C be any cycle, and let f be the max cost edge belonging 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*).!Contradicts minimality of T*. !f T*eSC18Cut PropertySimplifying assumption. All edge costs ce are distinct.Cut property. Let S be any subset of vertices, and let e be the min cost edge 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*).!Contradicts minimality of T*. !f MST T*eScycle C 19introductionweighted graph APIcycles and cutsKruskal’s algorithmPrim’s algorithmadvanced algorithmsclustering20Kruskal's algorithm. [Kruskal, 1956] Consider edges in ascending order of 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-721Kruskal's algorithm example25%50%75%100%22wvCeKruskal's algorithm correctness proofTheorem. Kruskal's algorithm computes the MST.Pf. [case 1] Suppose that adding e to T creates a cycle C!e is the max weight
View Full Document
Unlocking...