KruskalMST.java

public class KruskalMST {

    private Queue<Edge> mst;

    public KruskalMST(EdgeWeightedGraph G) {

        mst = new LinkedList<Edge>();

        PriorityQueue<Edge> pq = new PriorityQueue<>();

        for(Edge e: G.edges()) pq.add(e);

        UF uf = new UF(G.V());

        while(!pq.isEmpty() && mst.size() < G.V() - 1) {

            Edge e = pq.poll();

            int v = e.either(), w = e.other(v);

            if(uf.isConnected(v, w)) continue;

            uf.union(v, w);

            mst.add(e);

        }

    }

    public Iterable<Edge> edges() {return mst;}

}