001// Exercise 4.3.21 4.3.22 (Solution published at http://algs4.cs.princeton.edu/) 002package algs43; 003import stdlib.*; 004import algs13.Queue; 005import algs15.WeightedUF; 006import algs24.IndexMinPQ; 007/* **************************************************************************** 008 * Compilation: javac PrimMST.java 009 * Execution: java PrimMST filename.txt 010 * Dependencies: EdgeWeightedGraph.java Edge.java Queue.java 011 * IndexMinPQ.java UF.java In.java StdOut.java 012 * Data files: http://algs4.cs.princeton.edu/43mst/tinyEWG.txt 013 * http://algs4.cs.princeton.edu/43mst/mediumEWG.txt 014 * http://algs4.cs.princeton.edu/43mst/largeEWG.txt 015 * 016 * Compute a minimum spanning forest using Prim's algorithm. 017 * 018 * % java PrimMST tinyEWG.txt 019 * 1-7 0.19000 020 * 0-2 0.26000 021 * 2-3 0.17000 022 * 4-5 0.35000 023 * 5-7 0.28000 024 * 6-2 0.40000 025 * 0-7 0.16000 026 * 1.81000 027 * 028 * % java PrimMST mediumEWG.txt 029 * 1-72 0.06506 030 * 2-86 0.05980 031 * 3-67 0.09725 032 * 4-55 0.06425 033 * 5-102 0.03834 034 * 6-129 0.05363 035 * 7-157 0.00516 036 * ... 037 * 10.46351 038 * 039 * % java PrimMST largeEWG.txt 040 * ... 041 * 647.66307 042 * 043 ******************************************************************************/ 044 045public class PrimMST { 046 private final Edge[] edgeTo; // edgeTo[v] = shortest edge from tree vertex to non-tree vertex 047 private final double[] distTo; // distTo[v] = weight of shortest such edge 048 private final boolean[] marked; // marked[v] = true if v on tree, false otherwise 049 private final IndexMinPQ<Double> pq; 050 051 public PrimMST(EdgeWeightedGraph G) { 052 edgeTo = new Edge[G.V()]; 053 distTo = new double[G.V()]; 054 marked = new boolean[G.V()]; 055 pq = new IndexMinPQ<>(G.V()); 056 for (int v = 0; v < G.V(); v++) distTo[v] = Double.POSITIVE_INFINITY; 057 058 for (int v = 0; v < G.V(); v++) // run from each vertex to find 059 if (!marked[v]) prim(G, v); // minimum spanning forest 060 061 // check optimality conditions 062 assert check(G); 063 } 064 065 // run Prim's algorithm in graph G, starting from vertex s 066 private void prim(EdgeWeightedGraph G, int s) { 067 distTo[s] = 0.0; 068 pq.insert(s, distTo[s]); 069 while (!pq.isEmpty()) { 070 int v = pq.delMin(); 071 scan(G, v); 072 } 073 } 074 075 // scan vertex v 076 private void scan(EdgeWeightedGraph G, int v) { 077 marked[v] = true; 078 for (Edge e : G.adj(v)) { 079 int w = e.other(v); 080 if (marked[w]) continue; // v-w is obsolete edge 081 if (e.weight() < distTo[w]) { 082 distTo[w] = e.weight(); 083 edgeTo[w] = e; 084 if (pq.contains(w)) pq.decreaseKey(w, distTo[w]); 085 else pq.insert(w, distTo[w]); 086 } 087 } 088 } 089 090 // return iterator of edges in MST 091 public Iterable<Edge> edges() { 092 Queue<Edge> mst = new Queue<>(); 093 for (Edge e : edgeTo) { 094 if (e != null) { 095 mst.enqueue(e); 096 } 097 } 098 return mst; 099 } 100 101 102 // return weight of MST 103 public double weight() { 104 double weight = 0.0; 105 for (Edge e : edges()) 106 weight += e.weight(); 107 return weight; 108 } 109 110 111 // check optimality conditions (takes time proportional to E V lg* V) 112 private boolean check(EdgeWeightedGraph G) { 113 114 // check weight 115 double totalWeight = 0.0; 116 for (Edge e : edges()) { 117 totalWeight += e.weight(); 118 } 119 double EPSILON = 1E-12; 120 if (Math.abs(totalWeight - weight()) > EPSILON) { 121 System.err.format("Weight of edges does not equal weight(): %f vs. %f\n", totalWeight, weight()); 122 return false; 123 } 124 125 // check that it is acyclic 126 WeightedUF uf = new WeightedUF(G.V()); 127 for (Edge e : edges()) { 128 int v = e.either(), w = e.other(v); 129 if (uf.connected(v, w)) { 130 System.err.println("Not a forest"); 131 return false; 132 } 133 uf.union(v, w); 134 } 135 136 // check that it is a spanning forest 137 for (Edge e : edges()) { 138 int v = e.either(), w = e.other(v); 139 if (!uf.connected(v, w)) { 140 System.err.println("Not a spanning forest"); 141 return false; 142 } 143 } 144 145 // check that it is a minimal spanning forest (cut optimality conditions) 146 for (Edge e : edges()) { 147 int v = e.either(), w = e.other(v); 148 149 // all edges in MST except e 150 uf = new WeightedUF(G.V()); 151 for (Edge f : edges()) { 152 int x = f.either(), y = f.other(x); 153 if (f != e) uf.union(x, y); 154 } 155 156 // check that e is min weight edge in crossing cut 157 for (Edge f : G.edges()) { 158 int x = f.either(), y = f.other(x); 159 if (!uf.connected(x, y)) { 160 if (f.weight() < e.weight()) { 161 System.err.println("Edge " + f + " violates cut optimality conditions"); 162 return false; 163 } 164 } 165 } 166 167 } 168 169 return true; 170 } 171 172 173 public static void main(String[] args) { 174 args = new String[] { "data/10000EWG.txt" }; 175 //args = new String[] { "data/mediumEWG.txt" }; 176 //args = new String[] { "data/largeEWG.txt" }; 177 In in = new In(args[0]); 178 EdgeWeightedGraph G = new EdgeWeightedGraph(in); 179 PrimMST mst = new PrimMST(G); 180 for (Edge e : mst.edges()) { 181 StdOut.println(e); 182 } 183 StdOut.format("%.5f\n", mst.weight()); 184 } 185 186 187}