-
Notifications
You must be signed in to change notification settings - Fork 197
/
Copy pathBoruvkaMST.java
190 lines (169 loc) · 6.54 KB
/
BoruvkaMST.java
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
/*************************************************************************
* Compilation: javac BoruvkaMST.java
* Execution: java BoruvkaMST filename.txt
* Dependencies: EdgeWeightedGraph.java Edge.java Bag.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 Boruvka's algorithm.
*
* % java BoruvkaMST tinyEWG.txt
* 0-2 0.26000
* 6-2 0.40000
* 5-7 0.28000
* 4-5 0.35000
* 2-3 0.17000
* 1-7 0.19000
* 0-7 0.16000
* 1.81000
*
*************************************************************************/
/**
* The <tt>BoruvkaMST</tt> class represents a data type for computing a
* <em>minimum spanning tree</em> 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 <em>minimum
* spanning forest</em>, which is the union of minimum spanning trees
* in each connected component. The <tt>weight()</tt> method returns the
* weight of a minimum spanning tree and the <tt>edges()</tt> method
* returns its edges.
* <p>
* This implementation uses <em>Boruvka's algorithm</em> and the union-find
* data type.
* The constructor takes time proportional to <em>E</em> log <em>V</em>
* and extra space (not including the graph) proportional to <em>V</em>,
* where <em>V</em> is the number of vertices and <em>E</em> is the number of edges.
* Afterwards, the <tt>weight()</tt> method takes constant time
* and the <tt>edges()</tt> method takes time proportional to <em>V</em>.
* <p>
* For additional documentation, see <a href="/algs4/44sp">Section 4.4</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
* For alternate implementations, see {@link LazyPrimMST}, {@link PrimMST},
* and {@link KruskalMST}.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class BoruvkaMST {
private Bag<Edge> mst = new Bag<Edge>(); // edges in MST
private double weight; // weight of MST
/**
* Compute a minimum spanning tree (or forest) of an edge-weighted graph.
* @param G the edge-weighted graph
*/
public BoruvkaMST(EdgeWeightedGraph G) {
UF uf = new UF(G.V());
// repeat at most log V times or until we have V-1 edges
for (int t = 1; t < G.V() && mst.size() < G.V() - 1; t = t + t) {
// foreach tree in forest, find closest edge
// if edge weights are equal, ties are broken in favor of first edge in G.edges()
Edge[] closest = new Edge[G.V()];
for (Edge e : G.edges()) {
int v = e.either(), w = e.other(v);
int i = uf.find(v), j = uf.find(w);
if (i == j) continue; // same tree
if (closest[i] == null || less(e, closest[i])) closest[i] = e;
if (closest[j] == null || less(e, closest[j])) closest[j] = e;
}
// add newly discovered edges to MST
for (int i = 0; i < G.V(); i++) {
Edge e = closest[i];
if (e != null) {
int v = e.either(), w = e.other(v);
// don't add the same edge twice
if (!uf.connected(v, w)) {
mst.add(e);
weight += e.weight();
uf.union(v, w);
}
}
}
}
// check optimality conditions
assert check(G);
}
/**
* 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() {
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() {
return weight;
}
// is the weight of edge e strictly less than that of edge f?
private static boolean less(Edge e, Edge f) {
return e.weight() < f.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 : mst) {
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 <tt>BoruvkaMST</tt> data type.
*/
public static void main(String[] args) {
In in = new In(args[0]);
EdgeWeightedGraph G = new EdgeWeightedGraph(in);
BoruvkaMST mst = new BoruvkaMST(G);
for (Edge e : mst.edges()) {
StdOut.println(e);
}
StdOut.printf("%.5f\n", mst.weight());
}
}