001package algs43; 002import stdlib.*; 003import algs13.Queue; 004import algs15.WeightedUF; 005import algs24.MinPQ; 006/* *********************************************************************** 007 * Compilation: javac LazyPrimMST.java 008 * Execution: java LazyPrimMST filename.txt 009 * Dependencies: EdgeWeightedGraph.java Edge.java Queue.java 010 * MinPQ.java 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 a lazy version of Prim's 016 * algorithm. 017 * 018 * % java LazyPrimMST tinyEWG.txt 019 * 0-7 0.16000 020 * 1-7 0.19000 021 * 0-2 0.26000 022 * 2-3 0.17000 023 * 5-7 0.28000 024 * 4-5 0.35000 025 * 6-2 0.40000 026 * 1.81000 027 * 028 * % java LazyPrimMST mediumEWG.txt 029 * 0-225 0.02383 030 * 49-225 0.03314 031 * 44-49 0.02107 032 * 44-204 0.01774 033 * 49-97 0.03121 034 * 202-204 0.04207 035 * 176-202 0.04299 036 * 176-191 0.02089 037 * 68-176 0.04396 038 * 58-68 0.04795 039 * 10.46351 040 * 041 * % java LazyPrimMST largeEWG.txt 042 * ... 043 * 647.66307 044 * 045 *************************************************************************/ 046 047public class LazyPrimMST { 048 private double weight; // total weight of MST 049 private final Queue<Edge> mst; // edges in the MST 050 private final boolean[] marked; // marked[v] = true if v on tree 051 private final MinPQ<Edge> pq; // edges with one endpoint in tree 052 053 // compute minimum spanning forest of G 054 public LazyPrimMST(EdgeWeightedGraph G) { 055 mst = new Queue<>(); 056 pq = new MinPQ<>(); 057 marked = new boolean[G.V()]; 058 for (int v = 0; v < G.V(); v++) // run Prim from all vertices to 059 if (!marked[v]) prim(G, v); // get a minimum spanning forest 060 061 // check optimality conditions 062 assert check(G); 063 } 064 065 // run Prim's algorithm 066 private void prim(EdgeWeightedGraph G, int s) { 067 scan(G, s); 068 while (!pq.isEmpty()) { // better to stop when mst has V-1 edges 069 Edge e = pq.delMin(); // smallest edge on pq 070 int v = e.either(), w = e.other(v); // two endpoints 071 assert marked[v] || marked[w]; 072 if (marked[v] && marked[w]) continue; // lazy, both v and w already scanned 073 mst.enqueue(e); // add e to MST 074 weight += e.weight(); 075 if (!marked[v]) scan(G, v); // v becomes part of tree 076 if (!marked[w]) scan(G, w); // w becomes part of tree 077 } 078 } 079 080 // add all edges e incident to v onto pq if the other endpoint has not yet been scanned 081 private void scan(EdgeWeightedGraph G, int v) { 082 assert !marked[v]; 083 marked[v] = true; 084 for (Edge e : G.adj(v)) 085 if (!marked[e.other(v)]) pq.insert(e); 086 } 087 088 // return edges in MST as an Iterable 089 public Iterable<Edge> edges() { 090 return mst; 091 } 092 093 // return weight of MST 094 public double weight() { 095 return weight; 096 } 097 098 // check optimality conditions (takes time proportional to E V lg* V) 099 private boolean check(EdgeWeightedGraph G) { 100 101 // check weight 102 double totalWeight = 0.0; 103 for (Edge e : edges()) { 104 totalWeight += e.weight(); 105 } 106 double EPSILON = 1E-12; 107 if (Math.abs(totalWeight - weight()) > EPSILON) { 108 System.err.format("Weight of edges does not equal weight(): %f vs. %f\n", totalWeight, weight()); 109 return false; 110 } 111 112 // check that it is acyclic 113 WeightedUF uf = new WeightedUF(G.V()); 114 for (Edge e : edges()) { 115 int v = e.either(), w = e.other(v); 116 if (uf.connected(v, w)) { 117 System.err.println("Not a forest"); 118 return false; 119 } 120 uf.union(v, w); 121 } 122 123 // check that it is a spanning forest 124 for (Edge e : edges()) { 125 int v = e.either(), w = e.other(v); 126 if (!uf.connected(v, w)) { 127 System.err.println("Not a spanning forest"); 128 return false; 129 } 130 } 131 132 // check that it is a minimal spanning forest (cut optimality conditions) 133 for (Edge e : edges()) { 134 int v = e.either(), w = e.other(v); 135 136 // all edges in MST except e 137 uf = new WeightedUF(G.V()); 138 for (Edge f : mst) { 139 int x = f.either(), y = f.other(x); 140 if (f != e) uf.union(x, y); 141 } 142 143 // check that e is min weight edge in crossing cut 144 for (Edge f : G.edges()) { 145 int x = f.either(), y = f.other(x); 146 if (!uf.connected(x, y)) { 147 if (f.weight() < e.weight()) { 148 System.err.println("Edge " + f + " violates cut optimality conditions"); 149 return false; 150 } 151 } 152 } 153 154 } 155 156 return true; 157 } 158 159 160 public static void main(String[] args) { 161 In in = new In(args[0]); 162 EdgeWeightedGraph G = new EdgeWeightedGraph(in); 163 LazyPrimMST mst = new LazyPrimMST(G); 164 for (Edge e : mst.edges()) { 165 StdOut.println(e); 166 } 167 StdOut.format("%.5f\n", mst.weight()); 168 } 169 170}