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