-
Notifications
You must be signed in to change notification settings - Fork 4
/
PrimMST.java
241 lines (199 loc) · 7.05 KB
/
PrimMST.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
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
package algorithms.mst;
import java.util.*;
public class PrimMST {
public static void main(String[] args) {
undirectedExample();
}
private static void undirectedExample() {
/**
* 0
* (B) ---- (E)
* /| | \
* 10 / | 3 1 | \ 8
* / | | \
* / 1 | 8 | 9 \
* (A)-----(C)------(F)------(H)
* \ | /| /
* 4 \ 2| 2/ |6 / 12
* \ | / | /
* \ | / |/
* (D)------(G)
* 7
*
* Starting from A (doesn't make a difference)
* A->C = 1
* C->D = 2
* D->F = 2
* F->E = 1
* E->B = 0
* F->G = 6
* E->H = 8
* --------
* TOTAL = 20
*/
Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D");
Node nodeE = new Node("E");
Node nodeF = new Node("F");
Node nodeG = new Node("G");
Node nodeH = new Node("H");
// Node A's adjacency
nodeA.addNeighbour(new Edge(10, nodeA, nodeB));
nodeA.addNeighbour(new Edge(1, nodeA, nodeC));
nodeA.addNeighbour(new Edge(4, nodeA, nodeD));
// Node B's adjacency
nodeB.addNeighbour(new Edge(10, nodeB, nodeA));
nodeB.addNeighbour(new Edge(3, nodeB, nodeC));
nodeB.addNeighbour(new Edge(0, nodeB, nodeE));
// Node C's adjacency
nodeC.addNeighbour(new Edge(1, nodeC, nodeA));
nodeC.addNeighbour(new Edge(3, nodeC, nodeB));
nodeC.addNeighbour(new Edge(2, nodeC, nodeD));
nodeC.addNeighbour(new Edge(8, nodeC, nodeF));
// Node D's adjacency
nodeD.addNeighbour(new Edge(4, nodeD, nodeA));
nodeD.addNeighbour(new Edge(2, nodeD, nodeC));
nodeD.addNeighbour(new Edge(2, nodeD, nodeF));
nodeD.addNeighbour(new Edge(7, nodeD, nodeG));
// Node E's adjacency
nodeE.addNeighbour(new Edge(0, nodeE, nodeB));
nodeE.addNeighbour(new Edge(1, nodeE, nodeF));
nodeE.addNeighbour(new Edge(8, nodeE, nodeH));
// Node F's adjacency
nodeF.addNeighbour(new Edge(1, nodeF, nodeE));
nodeF.addNeighbour(new Edge(8, nodeF, nodeC));
nodeF.addNeighbour(new Edge(2, nodeF, nodeD));
nodeF.addNeighbour(new Edge(6, nodeF, nodeG));
nodeF.addNeighbour(new Edge(9, nodeF, nodeH));
// Node G's adjacency
nodeG.addNeighbour(new Edge(7, nodeG, nodeD));
nodeG.addNeighbour(new Edge(6, nodeG, nodeF));
nodeG.addNeighbour(new Edge(12, nodeG, nodeH));
// Node H's adjacency
nodeH.addNeighbour(new Edge(8, nodeH, nodeE));
nodeH.addNeighbour(new Edge(9, nodeH, nodeF));
nodeH.addNeighbour(new Edge(12, nodeH, nodeG));
PrimMST primMST = new PrimMST();
primMST.computeMST(nodeA);
}
private void computeMST(Node sourceNode) {
Queue<Edge> pq = new PriorityQueue<>();
for (Edge edge : sourceNode.getAdjacencyList()) {
pq.add(edge);
}
sourceNode.setVisited(true);
int minCost = 0;
while ( ! pq.isEmpty()) {
Edge currentEdge = pq.poll();
if (currentEdge.destinationNode.isVisited()) {
continue;
}
currentEdge.destinationNode.setVisited(true);
System.out.println("currentEdge = " + currentEdge);
minCost += currentEdge.getWeight();
for (Edge adjEdgeOfCurrEdgesDestNode : currentEdge.getDestinationNode().getAdjacencyList()) {
pq.add(adjEdgeOfCurrEdgesDestNode);
}
}
System.out.println("minCost = " + minCost);
}
private static void Prim() {
}
static class Node implements Comparable<Node> {
private String name;
private List<Edge> adjacencyList;
private boolean visited;
private Node prevNode;
private double totalWeight;
public Node(String name) {
this.name = name;
this.adjacencyList = new ArrayList<>();
this.totalWeight = Double.MAX_VALUE;
}
public void addNeighbour (Edge edge) {
this.adjacencyList.add(edge);
}
@Override
public String toString() {
return this.name;
}
@Override
public int compareTo(Node otherNode) {
// returns -1 when this.totalWeight < otherNode.getTotalWeight()
// returns 1 when this.totalWeight > otherNode.getTotalWeight()
return Double.compare(this.totalWeight, otherNode.getTotalWeight());
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public List<Edge> getAdjacencyList() {
return adjacencyList;
}
public void setAdjacencyList(List<Edge> adjacencyList) {
this.adjacencyList = adjacencyList;
}
public boolean isVisited() {
return visited;
}
public void setVisited(boolean visited) {
this.visited = visited;
}
public Node getPrevNode() {
return prevNode;
}
public void setPrevNode(Node prevNode) {
this.prevNode = prevNode;
}
public double getTotalWeight() {
return totalWeight;
}
public void setTotalWeight(double totalWeight) {
this.totalWeight = totalWeight;
}
}
public static class Edge implements Comparable<Edge> {
private double weight;
private Node sourceNode;
private Node destinationNode;
public Edge(double weight, Node sourceNode, Node destinationNode) {
this.weight = weight;
this.sourceNode = sourceNode;
this.destinationNode = destinationNode;
}
public double getWeight() {
return weight;
}
public void setWeight(double weight) {
this.weight = weight;
}
public Node getSourceNode() {
return sourceNode;
}
public void setSourceNode(Node sourceNode) {
this.sourceNode = sourceNode;
}
public Node getDestinationNode() {
return destinationNode;
}
public void setDestinationNode(Node destinationNode) {
this.destinationNode = destinationNode;
}
@Override
public int compareTo(Edge otherEdge) {
return Double.compare(this.weight, otherEdge.getWeight());
}
@Override
public String toString() {
return "Edge{" +
"weight=" + weight +
", sourceNode=" + sourceNode +
", destinationNode=" + destinationNode +
'}';
}
}
}