Implementing Prim's MST in Java

Question

I'm having trouble getting my code to follow CLRS's example of a Minimum Spanning Tree (MST) in page 635. I'm also implementing CLRS's pseudo-code for MST-Prim quite literally, which is

In particular, I'm implementing the following graph using an adjacency list:

So I actually have two issues. The first is that after adding the node b to the MST, my code picks as next element in the PriorityQueue node h instead of node c. I'm not sure how Java's implementation picks elements in case of ties, so if there's something I can do about this please advise. To temporarily circumvent this issue I modified the edge a-h to have a weight of 9.

Everything then runs fine until it picks node d instead of g after adding f to the MST, which I find really strange since the PriorityQueue clearly has g with key=6.

My implementation is below:

import java.util.LinkedList;
import java.util.PriorityQueue;

class Edge{

    private Node source;
    private Node destination;
    private int weight;

    public void setSource(Node source) {
        this.source = source;
    }

    public void setDestination(Node destination) {
        this.destination = destination;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    public int getWeight() {
        return this.weight;
    }

    public Node getSource() {
        return this.source;
    }

    public Node getDestination() {
        return this.destination;
    }

}

class Node implements Comparable<Node>{
    private String label;
    private LinkedList<Edge> edges;
    private int key;
    private Node daddy;

    Node() {
        this.edges = new LinkedList();
    }

    public void setLabel(String label) {
        this.label = label;
    }

    public void setKey(int key) {
        this.key = key;
    }

    public void setDaddy(Node daddy) {
        this.daddy = daddy;
    }

    public String getLabel() {
        return this.label;
    }

    public int getKey() { return this.key; }

    public LinkedList getEdges() {
        return this.edges;
    }

    @Override
    public int compareTo(Node o) {
        if (this.getKey() > o.getKey()) {
            return 1;
        }
        else if (this.getKey() < o.getKey()) {
            return -1;
        }
        else {
            return 0;
        }
    }
}

public class Graph {

    private int numberOfNodes;
    private Node[] weightedGraph;

    public Graph(int graphV) {

        this.numberOfNodes = graphV;
        this.weightedGraph = new Node[this.numberOfNodes];
        for (int i = 0; i < this.numberOfNodes; i++) {
            this.weightedGraph[i] = new Node();
        }
    }

    public void addEdge(String sourceLabel, String destinationLabel, int weight) {

        Node sourceNode = null;
        Node destinationNode = null;

        for (Node node: this.weightedGraph) {
            if (node.getLabel().contains(sourceLabel)) {
                sourceNode = node;
            }
            if (node.getLabel().contains(destinationLabel)) {
                destinationNode = node;
            }
        }

        Edge e = new Edge();
        e.setWeight(weight);
        e.setSource(sourceNode);
        e.setDestination(destinationNode);
        sourceNode.getEdges().add(e);

    }

    public void minimumSpanningTree(String root) {
        Node rootNode = null;
        for (Node vertex: this.weightedGraph) {
            vertex.setKey(Integer.MAX_VALUE);
            vertex.setDaddy(null);
            if (vertex.getLabel().contains(root)) {
                rootNode = vertex;
            }
        }

        rootNode.setKey(0);

        PriorityQueue<Node> nodePriorityQueue = new PriorityQueue<>();

        for (Node vertex: this.weightedGraph) {
            nodePriorityQueue.add(vertex);
        }
        int min = 0;
        while (!nodePriorityQueue.isEmpty()) {

            Node u = nodePriorityQueue.peek();

            LinkedList<Edge> uEdges= u.getEdges();
            for (Edge e: uEdges) {
                Node v = e.getDestination();
                int u_vWeight = e.getWeight();
                if (nodePriorityQueue.contains(e.getDestination()) && u_vWeight < v.getKey()) {
                    v.setDaddy(u);
                    v.setKey(u_vWeight);
                }
            }
            nodePriorityQueue.remove(u);
            min += u.getKey();
        }

    }

    public static void main(String[] args) {

        Graph graph = new Graph(9);
        String[] nodes = new String[9];
        nodes[0] = "a";
        nodes[1] = "b";
        nodes[2] = "c";
        nodes[3] = "d";
        nodes[4] = "e";
        nodes[5] = "f";
        nodes[6] = "g";
        nodes[7] = "h";
        nodes[8] = "i";
        int pos = 0;
        for (String s: nodes) {
            graph.weightedGraph[pos].setLabel(s);
            pos += 1;
        }

        graph.addEdge("a", "b", 4);
        graph.addEdge("a", "h", 9);
        graph.addEdge("b", "h", 11);
        graph.addEdge("b", "c", 8);
        graph.addEdge("h", "i", 7);
        graph.addEdge("i", "g", 6);
        graph.addEdge("c", "f", 4);
        graph.addEdge("c", "d", 7);
        graph.addEdge("d", "e", 9);
        graph.addEdge("d", "f", 14);
        graph.addEdge("e", "f", 10);
        graph.addEdge("h", "g", 1);
        graph.addEdge("c", "i", 2);
        graph.addEdge("g", "f", 2);

        graph.minimumSpanningTree("a");


    }
}

Essentially I have three classes, Node, Edge and Graph. I included a Comparator in Node to allow the PriorityQueue to reorder elements as needed.

I build the graph, call minimumSpanningTree, which prints the following MST:

a
b
c
i
f
d
e
h
g

Instead of doing a-b-c-i-f-g as in CLRS's example which I show below:

I don't really understand why it's picking node d instead of g when g clearly has the lowest key, which inspecting by debugging the priorityQueue corroborates.

Help is greatly appreciated.

Answer 1

I figured out my problem. It turns out that the edges in the adjacency list representation I built are directed. To solve this I just added the reverse edges and everything works as expected.

And it also turns out that the priority queue does not update its elements upon removal of one of them. According to some other answers on SO about priority queues (PQ) not updating, I removed and added the nodes from the PQ whose keys are updated inside the for loop. Does anyone have a better suggestion? Updated code of minimumSpanningTree is below:

public void minimumSpanningTree(String root) {

        ArrayList<Node> msTree = new ArrayList<>();

        Node rootNode = null;
        for (Node vertex: this.weightedGraph) {
            vertex.setKey(Integer.MAX_VALUE);
            vertex.setDaddy(null);
            if (vertex.getLabel().contains(root)) {
                rootNode = vertex;
            }
        }

        rootNode.setKey(0);

        PriorityQueue<Node> nodePriorityQueue = new PriorityQueue<>();

        for (Node vertex: this.weightedGraph) {
            nodePriorityQueue.add(vertex);
        }
        int min = 0;
        while (!nodePriorityQueue.isEmpty()) {

            Node u = nodePriorityQueue.peek();

            LinkedList<Edge> uEdges= u.getEdges();
            for (Edge e: uEdges) {
                Node v = e.getDestination();
                int u_vWeight = e.getWeight();
                if (nodePriorityQueue.contains(e.getDestination()) && u_vWeight < v.getKey()) {
                    nodePriorityQueue.remove(v);
                    v.setDaddy(u);
                    v.setKey(u_vWeight);
                    nodePriorityQueue.add(v);
                }
            }
            msTree.add(u);
            System.out.println(u.getLabel());
            nodePriorityQueue.remove(u);
        }

EDIT: However, I'm having the same problem with edges a-h and a-b. I think its still a MST, but is there a way I can prioritize visiting node b before h? I.e. in case of ties in the priority queue, prioritize a key with a lower alphanumeric priority?