001// Exercise 4.3.22 4.3.33 (Solution published at http://algs4.cs.princeton.edu/) 002package algs43; 003import stdlib.*; 004import algs13.Queue; 005import algs15.WeightedUF; 006import algs24.MinPQ; 007/* *********************************************************************** 008 * Compilation: javac KruskalMST.java 009 * Execution: java LazyPrimMST filename.txt 010 * Dependencies: EdgeWeightedGraph.java Edge.java Queue.java 011 * 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 Kruskal's algorithm. 017 * 018 * % java KruskalMST tinyEWG.txt 019 * 0-7 0.16000 020 * 2-3 0.17000 021 * 1-7 0.19000 022 * 0-2 0.26000 023 * 5-7 0.28000 024 * 4-5 0.35000 025 * 6-2 0.40000 026 * 1.81000 027 * 028 * % java KruskalMST mediumEWG.txt 029 * 168-231 0.00268 030 * 151-208 0.00391 031 * 7-157 0.00516 032 * 122-205 0.00647 033 * 8-152 0.00702 034 * 156-219 0.00745 035 * 28-198 0.00775 036 * 38-126 0.00845 037 * 10-123 0.00886 038 * ... 039 * 10.46351 040 * 041 *************************************************************************/ 042 043public class KruskalMST { 044 private double weight; // weight of MST 045 private final Queue<Edge> mst = new Queue<>(); // edges in MST 046 047 // Kruskal's algorithm 048 public KruskalMST(EdgeWeightedGraph G) { 049 // more efficient to build heap by passing array of edges 050 MinPQ<Edge> pq = new MinPQ<>(); 051 for (Edge e : G.edges()) { 052 pq.insert(e); 053 } 054 055 // run greedy algorithm 056 WeightedUF uf = new WeightedUF(G.V()); 057 while (!pq.isEmpty() && mst.size() < G.V() - 1) { 058 Edge e = pq.delMin(); 059 int v = e.either(); 060 int w = e.other(v); 061 if (!uf.connected(v, w)) { // v-w does not create a cycle 062 uf.union(v, w); // merge v and w components 063 mst.enqueue(e); // add edge e to mst 064 weight += e.weight(); 065 } 066 } 067 068 // check optimality conditions 069 assert check(G); 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 // check optimality conditions (takes time proportional to E V lg* V) 083 private boolean check(EdgeWeightedGraph G) { 084 085 // check total weight 086 double total = 0.0; 087 for (Edge e : edges()) { 088 total += e.weight(); 089 } 090 double EPSILON = 1E-12; 091 if (Math.abs(total - weight()) > EPSILON) { 092 System.err.format("Weight of edges does not equal weight(): %f vs. %f\n", total, weight()); 093 return false; 094 } 095 096 // check that it is acyclic 097 WeightedUF uf = new WeightedUF(G.V()); 098 for (Edge e : edges()) { 099 int v = e.either(), w = e.other(v); 100 if (uf.connected(v, w)) { 101 System.err.println("Not a forest"); 102 return false; 103 } 104 uf.union(v, w); 105 } 106 107 // check that it is a spanning forest 108 for (Edge e : edges()) { 109 int v = e.either(), w = e.other(v); 110 if (!uf.connected(v, w)) { 111 System.err.println("Not a spanning forest"); 112 return false; 113 } 114 } 115 116 // check that it is a minimal spanning forest (cut optimality conditions) 117 for (Edge e : edges()) { 118 int v = e.either(), w = e.other(v); 119 120 // all edges in MST except e 121 uf = new WeightedUF(G.V()); 122 for (Edge f : mst) { 123 int x = f.either(), y = f.other(x); 124 if (f != e) uf.union(x, y); 125 } 126 127 // check that e is min weight edge in crossing cut 128 for (Edge f : G.edges()) { 129 int x = f.either(), y = f.other(x); 130 if (!uf.connected(x, y)) { 131 if (f.weight() < e.weight()) { 132 System.err.println("Edge " + f + " violates cut optimality conditions"); 133 return false; 134 } 135 } 136 } 137 138 } 139 140 return true; 141 } 142 143 144 public static void main(String[] args) { 145 In in = new In(args[0]); 146 EdgeWeightedGraph G = new EdgeWeightedGraph(in); 147 KruskalMST mst = new KruskalMST(G); 148 for (Edge e : mst.edges()) { 149 StdOut.println(e); 150 } 151 StdOut.format("%.5f\n", mst.weight()); 152 } 153 154} 155