Below is the syntax highlighted version of BoruvkaMST.java.
/****************************************************************************** * Compilation: javac BoruvkaMST.java * Execution: java BoruvkaMST filename.txt * Dependencies: EdgeWeightedGraph.java Edge.java Bag.java * UF.java In.java StdOut.java * Data files: https://algs4.cs.princeton.edu/43mst/tinyEWG.txt * https://algs4.cs.princeton.edu/43mst/mediumEWG.txt * https://algs4.cs.princeton.edu/43mst/largeEWG.txt * * Compute a minimum spanning forest using Boruvka's algorithm. * * % java BoruvkaMST tinyEWG.txt * 0-2 0.26000 * 6-2 0.40000 * 5-7 0.28000 * 4-5 0.35000 * 2-3 0.17000 * 1-7 0.19000 * 0-7 0.16000 * 1.81000 * ******************************************************************************/ package edu.princeton.cs.algs4; /** * The {@code BoruvkaMST} class represents a data type for computing a * <em>minimum spanning tree</em> in an edge-weighted graph. * The edge weights can be positive, zero, or negative and need not * be distinct. If the graph is not connected, it computes a <em>minimum * spanning forest</em>, which is the union of minimum spanning trees * in each connected component. The {@code weight()} method returns the * weight of a minimum spanning tree and the {@code edges()} method * returns its edges. * <p> * This implementation uses <em>Boruvka's algorithm</em> and the union-find * data type. * The constructor takes Θ(<em>E</em> log <em>V</em>) time in * the worst case, where <em>V</em> is the number of vertices and * <em>E</em> is the number of edges. * Each instance method takes Θ(1) time. * It uses Θ(<em>V</em>) extra space (not including the * edge-weighted graph). * <p> * This {@code weight()} method correctly computes the weight of the MST * if all arithmetic performed is without floating-point rounding error * or arithmetic overflow. * This is the case if all edge weights are non-negative integers * and the weight of the MST does not exceed 2<sup>52</sup>. * <p> * For additional documentation, * see <a href="https://algs4.cs.princeton.edu/43mst">Section 4.3</a> of * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. * For alternate implementations, see {@link LazyPrimMST}, {@link PrimMST}, * and {@link KruskalMST}. * * @author Robert Sedgewick * @author Kevin Wayne */ public class BoruvkaMST { private static final double FLOATING_POINT_EPSILON = 1.0E-12; private Bag<Edge> mst = new Bag<Edge>(); // edges in MST private double weight; // weight of MST /** * Compute a minimum spanning tree (or forest) of an edge-weighted graph. * @param G the edge-weighted graph */ public BoruvkaMST(EdgeWeightedGraph G) { UF uf = new UF(G.V()); // repeat at most log V times or until we have V-1 edges for (int t = 1; t < G.V() && mst.size() < G.V() - 1; t = t + t) { // foreach tree in forest, find closest edge // if edge weights are equal, ties are broken in favor of first edge in G.edges() Edge[] closest = new Edge[G.V()]; for (Edge e : G.edges()) { int v = e.either(), w = e.other(v); int i = uf.find(v), j = uf.find(w); if (i == j) continue; // same tree if (closest[i] == null || less(e, closest[i])) closest[i] = e; if (closest[j] == null || less(e, closest[j])) closest[j] = e; } // add newly discovered edges to MST for (int i = 0; i < G.V(); i++) { Edge e = closest[i]; if (e != null) { int v = e.either(), w = e.other(v); // don't add the same edge twice if (uf.find(v) != uf.find(w)) { mst.add(e); weight += e.weight(); uf.union(v, w); } } } } // check optimality conditions assert check(G); } /** * Returns the edges in a minimum spanning tree (or forest). * @return the edges in a minimum spanning tree (or forest) as * an iterable of edges */ public Iterable<Edge> edges() { return mst; } /** * Returns the sum of the edge weights in a minimum spanning tree (or forest). * @return the sum of the edge weights in a minimum spanning tree (or forest) */ public double weight() { return weight; } // is the weight of edge e strictly less than that of edge f? private static boolean less(Edge e, Edge f) { return e.compareTo(f) < 0; } // check optimality conditions (takes time proportional to E V lg* V) private boolean check(EdgeWeightedGraph G) { // check weight double totalWeight = 0.0; for (Edge e : edges()) { totalWeight += e.weight(); } if (Math.abs(totalWeight - weight()) > FLOATING_POINT_EPSILON) { System.err.printf("Weight of edges does not equal weight(): %f vs. %f\n", totalWeight, weight()); return false; } // check that it is acyclic UF uf = new UF(G.V()); for (Edge e : edges()) { int v = e.either(), w = e.other(v); if (uf.find(v) == uf.find(w)) { System.err.println("Not a forest"); return false; } uf.union(v, w); } // check that it is a spanning forest for (Edge e : G.edges()) { int v = e.either(), w = e.other(v); if (uf.find(v) != uf.find(w)) { System.err.println("Not a spanning forest"); return false; } } // check that it is a minimal spanning forest (cut optimality conditions) for (Edge e : edges()) { // all edges in MST except e uf = new UF(G.V()); for (Edge f : mst) { int x = f.either(), y = f.other(x); if (f != e) uf.union(x, y); } // check that e is min weight edge in crossing cut for (Edge f : G.edges()) { int x = f.either(), y = f.other(x); if (uf.find(x) != uf.find(y)) { if (f.weight() < e.weight()) { System.err.println("Edge " + f + " violates cut optimality conditions"); return false; } } } } return true; } /** * Unit tests the {@code BoruvkaMST} data type. * * @param args the command-line arguments */ public static void main(String[] args) { In in = new In(args[0]); EdgeWeightedGraph G = new EdgeWeightedGraph(in); BoruvkaMST mst = new BoruvkaMST(G); for (Edge e : mst.edges()) { StdOut.println(e); } StdOut.printf("%.5f\n", mst.weight()); } } /****************************************************************************** * Copyright 2002-2022, Robert Sedgewick and Kevin Wayne. * * This file is part of algs4.jar, which accompanies the textbook * * Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne, * Addison-Wesley Professional, 2011, ISBN 0-321-57351-X. * http://algs4.cs.princeton.edu * * * algs4.jar is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * algs4.jar is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with algs4.jar. If not, see http://www.gnu.org/licenses. ******************************************************************************/