You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
222 lines
7.0 KiB
Java
222 lines
7.0 KiB
Java
|
|
|
|
import edu.princeton.cs.introcs.In;
|
|
import edu.princeton.cs.introcs.StdOut;
|
|
|
|
/******************************************************************************
|
|
* Compilation: javac PrimMST.java
|
|
* Execution: java PrimMST filename.txt
|
|
* Dependencies: EdgeWeightedGraph.java Edge.java Queue.java
|
|
* IndexMinPQ.java UF.java In.java StdOut.java
|
|
* Data files: http://algs4.cs.princeton.edu/43mst/tinyEWG.txt
|
|
* http://algs4.cs.princeton.edu/43mst/mediumEWG.txt
|
|
* http://algs4.cs.princeton.edu/43mst/largeEWG.txt
|
|
*
|
|
* Compute a minimum spanning forest using Prim's algorithm.
|
|
*
|
|
* % java PrimMST tinyEWG.txt
|
|
* 1-7 0.19000
|
|
* 0-2 0.26000
|
|
* 2-3 0.17000
|
|
* 4-5 0.35000
|
|
* 5-7 0.28000
|
|
* 6-2 0.40000
|
|
* 0-7 0.16000
|
|
* 1.81000
|
|
*
|
|
* % java PrimMST mediumEWG.txt
|
|
* 1-72 0.06506
|
|
* 2-86 0.05980
|
|
* 3-67 0.09725
|
|
* 4-55 0.06425
|
|
* 5-102 0.03834
|
|
* 6-129 0.05363
|
|
* 7-157 0.00516
|
|
* ...
|
|
* 10.46351
|
|
*
|
|
* % java PrimMST largeEWG.txt
|
|
* ...
|
|
* 647.66307
|
|
*
|
|
******************************************************************************/
|
|
|
|
/**
|
|
* The PrimMST class represents a data type for computing a
|
|
* minimum spanning tree in an edge-weighted graph.
|
|
* The edge weights can be positive, zero, or negative and need not
|
|
* be distinct. If the graph is not connected, it computes a minimum
|
|
* spanning forest , which is the union of minimum spanning trees
|
|
* in each connected component. The weight() method returns the
|
|
* weight of a minimum spanning tree and the edges() method
|
|
* returns its edges.
|
|
*
|
|
* This implementation uses Prim's algorithm with an indexed
|
|
* binary heap.
|
|
* The constructor takes time proportional to E log V
|
|
* and extra space (not including the graph) proportional to V ,
|
|
* where V is the number of vertices and E is the number of edges.
|
|
* Afterwards, the weight() method takes constant time
|
|
* and the edges() method takes time proportional to V .
|
|
*
|
|
* For additional documentation, see <a href="/algs4/44sp">Section 4.4</a> of
|
|
* Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
|
|
* For alternate implementations, see {@link LazyPrimMST}, {@link KruskalMST},
|
|
* and {@link BoruvkaMST}.
|
|
*
|
|
* @author Robert Sedgewick
|
|
* @author Kevin Wayne
|
|
*/
|
|
public class PrimMST {
|
|
private Edge[] edgeTo; // edgeTo[v] = shortest edge from tree vertex to non-tree vertex
|
|
private double[] distTo; // distTo[v] = weight of shortest such edge
|
|
private boolean[] marked; // marked[v] = true if v on tree, false otherwise
|
|
private IndexMinPQ<Double> pq;
|
|
|
|
/**
|
|
* Compute a minimum spanning tree (or forest) of an edge-weighted graph.
|
|
* @param G the edge-weighted graph
|
|
*/
|
|
public PrimMST(EdgeWeightedGraph G) {
|
|
edgeTo = new Edge[G.V()];
|
|
distTo = new double[G.V()];
|
|
marked = new boolean[G.V()];
|
|
pq = new IndexMinPQ<Double>(G.V());
|
|
for (int v = 0; v < G.V(); v++) distTo[v] = Double.POSITIVE_INFINITY;
|
|
|
|
for (int v = 0; v < G.V(); v++) // run from each vertex to find
|
|
if (!marked[v]) prim(G, v); // minimum spanning forest
|
|
|
|
// check optimality conditions
|
|
assert check(G);
|
|
}
|
|
|
|
// run Prim's algorithm in graph G, starting from vertex s
|
|
private void prim(EdgeWeightedGraph G, int s) {
|
|
distTo[s] = 0.0;
|
|
pq.insert(s, distTo[s]);
|
|
while (!pq.isEmpty()) {
|
|
int v = pq.delMin();
|
|
scan(G, v);
|
|
}
|
|
}
|
|
|
|
// scan vertex v
|
|
private void scan(EdgeWeightedGraph G, int v) {
|
|
marked[v] = true;
|
|
for (Edge e : G.adj(v)) {
|
|
int w = e.other(v);
|
|
if (marked[w]) continue; // v-w is obsolete edge
|
|
if (e.weight() < distTo[w]) {
|
|
distTo[w] = e.weight();
|
|
edgeTo[w] = e;
|
|
if (pq.contains(w)) pq.decreaseKey(w, distTo[w]);
|
|
else pq.insert(w, distTo[w]);
|
|
}
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Returns the edges in a minimum spanning tree (or forest).
|
|
* @return the edges in a minimum spanning tree (or forest) as
|
|
* an iterable of edges
|
|
*/
|
|
public Iterable<Edge> edges() {
|
|
Queue<Edge> mst = new Queue<Edge>();
|
|
for (int v = 0; v < edgeTo.length; v++) {
|
|
Edge e = edgeTo[v];
|
|
if (e != null) {
|
|
mst.enqueue(e);
|
|
}
|
|
}
|
|
return mst;
|
|
}
|
|
|
|
/**
|
|
* Returns the sum of the edge weights in a minimum spanning tree (or forest).
|
|
* @return the sum of the edge weights in a minimum spanning tree (or forest)
|
|
*/
|
|
public double weight() {
|
|
double weight = 0.0;
|
|
for (Edge e : edges())
|
|
weight += e.weight();
|
|
return weight;
|
|
}
|
|
|
|
|
|
// check optimality conditions (takes time proportional to E V lg* V)
|
|
private boolean check(EdgeWeightedGraph G) {
|
|
|
|
// check weight
|
|
double totalWeight = 0.0;
|
|
for (Edge e : edges()) {
|
|
totalWeight += e.weight();
|
|
}
|
|
double EPSILON = 1E-12;
|
|
if (Math.abs(totalWeight - weight()) > EPSILON) {
|
|
System.err.printf("Weight of edges does not equal weight(): %f vs. %f\n", totalWeight, weight());
|
|
return false;
|
|
}
|
|
|
|
// check that it is acyclic
|
|
UF uf = new UF(G.V());
|
|
for (Edge e : edges()) {
|
|
int v = e.either(), w = e.other(v);
|
|
if (uf.connected(v, w)) {
|
|
System.err.println("Not a forest");
|
|
return false;
|
|
}
|
|
uf.union(v, w);
|
|
}
|
|
|
|
// check that it is a spanning forest
|
|
for (Edge e : G.edges()) {
|
|
int v = e.either(), w = e.other(v);
|
|
if (!uf.connected(v, w)) {
|
|
System.err.println("Not a spanning forest");
|
|
return false;
|
|
}
|
|
}
|
|
|
|
// check that it is a minimal spanning forest (cut optimality conditions)
|
|
for (Edge e : edges()) {
|
|
|
|
// all edges in MST except e
|
|
uf = new UF(G.V());
|
|
for (Edge f : edges()) {
|
|
int x = f.either(), y = f.other(x);
|
|
if (f != e) uf.union(x, y);
|
|
}
|
|
|
|
// check that e is min weight edge in crossing cut
|
|
for (Edge f : G.edges()) {
|
|
int x = f.either(), y = f.other(x);
|
|
if (!uf.connected(x, y)) {
|
|
if (f.weight() < e.weight()) {
|
|
System.err.println("Edge " + f + " violates cut optimality conditions");
|
|
return false;
|
|
}
|
|
}
|
|
}
|
|
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
/**
|
|
* Unit tests the PrimMST data type.
|
|
*/
|
|
public static void main(String[] args) {
|
|
In in = new In(args[0]);
|
|
EdgeWeightedGraph G = new EdgeWeightedGraph(in);
|
|
PrimMST mst = new PrimMST(G);
|
|
for (Edge e : mst.edges()) {
|
|
StdOut.println(e);
|
|
}
|
|
StdOut.printf("%.5f\n", mst.weight());
|
|
}
|
|
|
|
|
|
}
|