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.