I have implemented Prim's Algorithm in Java. I am wondering how it can be made more efficient.
Below is the class Node
for vertices.
public class Node {
private final char label;
private final Map<Node, Integer> neighbourList;
public Node(char label) {
this.label = label;
this.neighbourList = new LinkedHashMap<>();
}
public void addNeighbourer(Node node, int weight) {
neighbourList.put(node, weight);
}
public char getLabel() {
return label;
}
public Map<Node, Integer> neighbourerList() {
return neighbourList;
}
}
Below is a Map freeMap
which contains all vertices with value Integer.MAX_VALUE
except for first vertex whose value is set to 0.
freeMap.put(nodeA, 0);
freeMap.put(nodeB, Integer.MAX_VALUE);
freeMap.put(nodeC, Integer.MAX_VALUE);
freeMap.put(nodeD, Integer.MAX_VALUE);
freeMap.put(nodeE, Integer.MAX_VALUE);
freeMap.put(nodeF, Integer.MAX_VALUE);
And below is Prim's Algorithm.
public void primMinimumWeightSpanningTree(Map<Node, Integer> freeMap) {
Set<Node> mstSet = new LinkedHashSet<>();
while (freeMap.size() > 0) {
Node minNode = null;
/* finds minimum node in freeMap as per corresponding value.*/
for (Map.Entry<Node, Integer> entry : freeMap.entrySet()) {
if (minNode == null) {
minNode = entry.getKey();
} else {
if (entry.getValue() < freeMap.get(minNode)) {
minNode = entry.getKey();
}
}
}
freeMap.remove(minNode); /* remove minimum node from freeMap*/
mstSet.add(minNode); /* add minimum node to MST set(mstSet)*/
/* update values of adjacent nodes in freeMap*/
for (Map.Entry<Node, Integer> entry : minNode.neighbourerList().entrySet()) {
if (freeMap.containsKey(entry.getKey())) {
int value = freeMap.get(entry.getKey());
if (value > entry.getValue()) {
freeMap.replace(entry.getKey(), entry.getValue());
}
}
}
}
/* display vertices once all are added to mstSet*/
for (Node node : mstSet) {
System.out.print(node.getLabel() + " ");
}
}