# Improving efficiency of Prim's Algorithm

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;
}

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) {

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*/
/* 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() + " ");
}
}


Single responsibility principle

The primMinimumWeightSpanningTree() is clearly doing to much.
It is

• finding the minimum node
• updating values in the freeMap
• displaying the result

You should extract the finding of the minimum node to a separate method. Also replacing the else with an else if will save one indention.

private Node getMinimumNode(Map<Node, Integer> freeMap){
Node minNode = null;

for (Map.Entry<Node, Integer> entry : freeMap.entrySet()) {
if (minNode == null) {
minNode = entry.getKey();
} else if (entry.getValue() < freeMap.get(minNode)){
minNode = entry.getKey();
}
}

return minNode;
}


To be able to display the result outside of this method, we need to return a Set<Node>.
So let us refactor

public Set<Node> getPrimMinimumWeightSpanningTree(Map<Node, Integer> freeMap) {

while (freeMap.size() > 0) {

Node minNode = getMinimumNode(freeMap);

freeMap.remove(minNode);

/* 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());
}
}
}
}

return mstSet;
}


and add a method for displaying

Public void displayResult(Set<Node> mstSet){

for (Node node : mstSet) {
System.out.print(node.getLabel() + " ");
}

}


You can also think about overriding toString() so you can decide outside of the class, if you want to print to System.out or e.g write to a file.

Style

Comments are useful, but only if they tell why something is done. So telling what is done, where it is clearly visible like

freeMap.remove(minNode); /* remove minimum node from freeMap*/