Improving efficiency of Prim's Algorithm

Question

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

Answer 1

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) {
 Set<Node> mstSet = new LinkedHashSet<>();
 while (freeMap.size() > 0) {
 Node minNode = getMinimumNode(freeMap);
 freeMap.remove(minNode);
 mstSet.add(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*/
mstSet.add(minNode); /* add minimum node to MST set(mstSet)* 

these comments are just useless and should be removed.

• Meena Chaudhary: Thanks for suggesting the changes. They made the code cleaner. Any input on increasing efficiency(time or space complexity of the code).