在 Java 中实施 Prim 的 MST

Question

我无法让我的代码遵循第 635 页中 CLRS 的最小生成树 (MST) 示例。我还从字面上实现了 CLRS 的 MST-Prim 伪代码，即

特别是，我使用邻接表实现了下图：

所以我实际上有两个问题。第一个是在将节点 b 添加到 MST 之后，我的代码选择作为 PriorityQueue 节点 h 而不是节点 c 中的下一个元素。我不确定 Java 的实现如何在出现关系的情况下选择元素，所以如果我能做些什么请告知。为了暂时规避这个问题，我修改了边 a-h 使其权重为 9。

然后一切正常，直到它在将 f 添加到 MST 之后选择节点 d 而不是 g，我觉得这很奇怪，因为 PriorityQueue 显然有 g 与 key=6。

我的实现如下：

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");


    }
}

基本上我有三个类、Node、Edge 和 Graph。我在 Node 中包含了一个 Comparator 以允许 PriorityQueue 根据需要重新排序元素。

我构建图表，调用 minimumSpanningTree，打印以下 MST：

a
b
c
i
f
d
e
h
g

而不是像我在下面显示的 CLRS 示例中那样执行 a-b-c-i-f-g：

我真的不明白为什么它选择节点 d 而不是 g 当 g 显然具有最低键时，通过调试 priorityQueue 检查证实了这一点。

非常感谢您的帮助。

Answer 1

我想通了我的问题。事实证明，我构建的邻接表表示中的边是有向的。为了解决这个问题，我只是添加了反向边缘，一切都按预期工作。

而且事实证明，优先级队列在删除其中一个元素后不会更新其元素。根据 SO 上关于优先级队列 (PQ) 未更新的一些其他答案，我从 PQ 中删除并添加了节点，这些节点的键在 for 循环内更新。有人有更好的建议吗？ minimumSpanningTree 的更新代码如下：

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

编辑：但是，我在边 a-h 和 a-b 上遇到了同样的问题。我认为它仍然是 MST，但有没有一种方法可以优先访问节点 b，然后再访问 h？ IE。如果优先级队列中有联系，优先考虑具有较低字母数字优先级的键？

在 Java 中实施 Prim 的 MST

Implementing Prim's MST in Java

java

minimum-spanning-tree

clrs