001// Exercise 4.3.43 (Solution published at http://algs4.cs.princeton.edu/) 002package algs43; 003import stdlib.*; 004import algs13.Bag; 005import algs15.WeightedUF; 006/* *********************************************************************** 007 * Compilation: javac BoruvkaMST.java 008 * Execution: java BoruvkaMST filename.txt 009 * Dependencies: EdgeWeightedGraph.java Edge.java Bag.java 010 * UF.java In.java StdOut.java 011 * Data files: http://algs4.cs.princeton.edu/43mst/tinyEWG.txt 012 * http://algs4.cs.princeton.edu/43mst/mediumEWG.txt 013 * http://algs4.cs.princeton.edu/43mst/largeEWG.txt 014 * 015 * Compute a minimum spanning forest using Boruvka's algorithm. 016 * 017 * % java BoruvkaMST tinyEWG.txt 018 * 0-2 0.26000 019 * 6-2 0.40000 020 * 5-7 0.28000 021 * 4-5 0.35000 022 * 2-3 0.17000 023 * 1-7 0.19000 024 * 0-7 0.16000 025 * 1.81000 026 * 027 *************************************************************************/ 028 029 030public class BoruvkaMST { 031 private final Bag<Edge> mst = new Bag<>(); // edges in MST 032 private double weight; // weight of MST 033 034 // Boruvka's algorithm 035 public BoruvkaMST(EdgeWeightedGraph G) { 036 WeightedUF uf = new WeightedUF(G.V()); 037 038 // repeat at most log V times or until we have V-1 edges 039 for (int t = 1; t < G.V() && mst.size() < G.V() - 1; t = t + t) { 040 041 // foreach tree in forest, find closest edge 042 // if edge weights are equal, ties are broken in favor of first edge in G.edges() 043 Edge[] closest = new Edge[G.V()]; 044 for (Edge e : G.edges()) { 045 int v = e.either(), w = e.other(v); 046 int i = uf.find(v), j = uf.find(w); 047 if (i == j) continue; // same tree 048 if (closest[i] == null || less(e, closest[i])) closest[i] = e; 049 if (closest[j] == null || less(e, closest[j])) closest[j] = e; 050 } 051 052 // add newly discovered edges to MST 053 for (int i = 0; i < G.V(); i++) { 054 Edge e = closest[i]; 055 if (e != null) { 056 int v = e.either(), w = e.other(v); 057 // don't add the same edge twice 058 if (!uf.connected(v, w)) { 059 mst.add(e); 060 weight += e.weight(); 061 uf.union(v, w); 062 } 063 } 064 } 065 } 066 067 // check optimality conditions 068 assert check(G); 069 } 070 071 072 // edges in minimum spanning forest, as an Iterable 073 public Iterable<Edge> edges() { 074 return mst; 075 } 076 077 // weight of minimum spanning forest 078 public double weight() { 079 return weight; 080 } 081 082 // is the weight of edge e strictly less than that of edge f? 083 private static boolean less(Edge e, Edge f) { 084 return e.weight() < f.weight(); 085 } 086 087 // check optimality conditions (takes time proportional to E V lg* V) 088 private boolean check(EdgeWeightedGraph G) { 089 090 // check weight 091 double totalWeight = 0.0; 092 for (Edge e : edges()) { 093 totalWeight += e.weight(); 094 } 095 double EPSILON = 1E-12; 096 if (Math.abs(totalWeight - weight()) > EPSILON) { 097 System.err.format("Weight of edges does not equal weight(): %f vs. %f\n", totalWeight, weight()); 098 return false; 099 } 100 101 // check that it is acyclic 102 WeightedUF uf = new WeightedUF(G.V()); 103 for (Edge e : edges()) { 104 int v = e.either(), w = e.other(v); 105 if (uf.connected(v, w)) { 106 System.err.println("Not a forest"); 107 return false; 108 } 109 uf.union(v, w); 110 } 111 112 // check that it is a spanning forest 113 for (Edge e : edges()) { 114 int v = e.either(), w = e.other(v); 115 if (!uf.connected(v, w)) { 116 System.err.println("Not a spanning forest"); 117 return false; 118 } 119 } 120 121 // check that it is a minimal spanning forest (cut optimality conditions) 122 for (Edge e : edges()) { 123 int v = e.either(), w = e.other(v); 124 125 // all edges in MST except e 126 uf = new WeightedUF(G.V()); 127 for (Edge f : mst) { 128 int x = f.either(), y = f.other(x); 129 if (f != e) uf.union(x, y); 130 } 131 132 // check that e is min weight edge in crossing cut 133 for (Edge f : G.edges()) { 134 int x = f.either(), y = f.other(x); 135 if (!uf.connected(x, y)) { 136 if (f.weight() < e.weight()) { 137 System.err.println("Edge " + f + " violates cut optimality conditions"); 138 return false; 139 } 140 } 141 } 142 143 } 144 145 return true; 146 } 147 148 public static void main(String[] args) { 149 In in = new In(args[0]); 150 EdgeWeightedGraph G = new EdgeWeightedGraph(in); 151 BoruvkaMST mst = new BoruvkaMST(G); 152 for (Edge e : mst.edges()) { 153 StdOut.println(e); 154 } 155 StdOut.format("%.5f\n", mst.weight()); 156 } 157 158}