-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMST.java
More file actions
119 lines (98 loc) · 3.84 KB
/
MST.java
File metadata and controls
119 lines (98 loc) · 3.84 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
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
package CommonUtils;
import CommonUtils.UsefulContainers.Edge;
import CommonUtils.UsefulContainers.iPair;
import java.util.ArrayList;
import java.util.List;
/**
* Class containing Minimum Spanning Tree (MST) utils. No interface provided because functions are static.
*
* <bold>251 students: You may only use java.util.List and java.util.ArrayList from the standard library.
* Any other containers used must be ones you created.</bold>
*/
public class MST {
/**
* Returns the MST of the given graph, optimized for a dense graph. Assumes a connected graph.
*
* @param weights square matrix representing positive edge weights between every vertex
* @return MST: list of pairs of indices each indicating an edge between those two indices
* @throws IllegalArgumentException if weights is not square or edges are not positive
*/
public static List<iPair> denseMST(double[][] weights) throws IllegalArgumentException {
// Validate weights matrix (already done)
int n = weights.length;
for (int i = 0; i < n; i++) {
if (weights[i].length != n)
throw new IllegalArgumentException("Weights graph not square in row " +
i + ", expected " + n + ", actual is " + weights[i].length);
for (int j = 0; j < n; j++) {
if (weights[i][j] < 0)
throw new IllegalArgumentException("Edge weight < 0 (" +
weights[i][j] + ") at y, x=" + i + ", " + j);
}
}
double[] dist = new double[n];
int[] edge = new int[n];
boolean[] visited = new boolean[n];
MinHeapWithUpdate<Double, Integer> Q = new MinHeapWithUpdate<>();
// Initialize dist, edge, visited arrays
for (int i = 0; i < n; i++) {
dist[i] = Double.POSITIVE_INFINITY;
edge[i] = -1;
visited[i] = false;
}
// Start at index 0
dist[0] = 0;
Q.add(0.0, 0);
while (Q.size() > 0) {
var p = Q.removeMin();
int u = p.b;
visited[u] = true;
for (int v = 0; v < n; v++) {
if (visited[v]) continue;
double weight = weights[u][v];
if (weight >= dist[v]) continue;
edge[v] = u;
dist[v] = weight;
Q.upsert(weight, v);
}
}
// Return all found edges
ArrayList<iPair> ret = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (edge[i] == -1) continue;
ret.add(new iPair(i, edge[i]));
}
return ret;
}
/**
* Returns the MST of the given graph, optimized for a sparse graph. Assumes a connected graph.
*
* @param edgeList edge list
* @param n number of vertices
* @return MST: list of pairs of indices each indicating an edge between those two indices
* @throws IllegalArgumentException if edges are not positive
*/
public static List<iPair> sparseMST(List<Edge> edgeList, int n) throws IllegalArgumentException {
// Validate edge weights (already done)
for (var e : edgeList) {
if (e.w < 0)
throw new IllegalArgumentException("Edge weight < 0 (" + e.w + ") between " + e.a + " and " + e.b);
}
MinHeap<Edge> Q = new MinHeap<>();
DisjointSet ds = new DisjointSet(n);
for (var e : edgeList) {
Q.add(e);
}
ArrayList<iPair> T = new ArrayList<>();
while (T.size() < n - 1) {
var e = Q.removeMin();
// If `a` and `b` are already connected
int idA = ds.find(e.a);
int idB = ds.find(e.b);
if (idA == idB) continue;
T.add(new iPair(e.a, e.b));
ds.union(e.a, e.b);
}
return T;
}
}