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

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.

  • Thanks for suggesting the changes. They made the code cleaner. Any input on increasing efficiency(time or space complexity of the code). – Meena Chaudhary Dec 18 '14 at 17:43

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.