-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathPrimMST.java
More file actions
73 lines (61 loc) · 1.86 KB
/
Copy pathPrimMST.java
File metadata and controls
73 lines (61 loc) · 1.86 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.IndexMinPQ;
import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.StdOut;
/**
* Created by Mofeng on 2017/5/15.
*/
public class PrimMST {
private Edge[] edgeTo;
private double[] distTo;
private boolean[] marked;
private IndexMinPQ<Double> pq;
private double weight;
public PrimMST(EdgeWeightedGraph G) {
edgeTo = new Edge[G.V()];
distTo = new double[G.V()];
marked = new boolean[G.V()];
for (int v = 0; v < G.V(); v++)
distTo[v] = Double.POSITIVE_INFINITY;
pq = new IndexMinPQ<Double>(G.V());
distTo[0] = 0.0;
pq.insert(0, 0.0);
while (!pq.isEmpty())
visit(G, pq.delMin());
for (Edge e: edges()) {
weight += e.weight();
}
}
private void visit(EdgeWeightedGraph G, int v) {
marked[v] = true;
for (Edge e : G.adj(v)) {
int w = e.other(v);
if (marked[w]) continue;
if (e.weight() < distTo[w]) {
edgeTo[w] = e;
distTo[w] = e.weight();
if (pq.contains(w)) pq.changeKey(w, distTo[w]);
else pq.insert(w, distTo[w]);
}
}
}
public Iterable<Edge> edges() {
Queue<Edge> mst = new Queue<Edge>();
for (int v = 0; v < edgeTo.length; v++) {
if(edgeTo[v] != null)
mst.enqueue(edgeTo[v]);
}
return mst;
}
public double weight() {
return weight;
}
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("mst Weight = %.2f\n", mst.weight());
}
}