时间戳

首页 > 解决方案 > 在 Java 中实现 Prim 的 MST

java - 在 Java 中实现 Prim 的 MST

问题描述

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

在此处输入图像描述

特别是，我正在使用邻接列表实现下图：在此处输入图像描述

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

然后一切都运行良好，直到它选择节点d而不是g添加f到 MST 之后，我觉得这很奇怪，因为 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。我Comparator在 Node 中包含了一个，以允许 PriorityQueue 根据需要重新排序元素。

我构建了图表 call minimumSpanningTree，它打印了以下 MST：

a
b
c
i
f
d
e
h
g

而不是a-b-c-i-f-g像我在下面显示的 CLRS 示例中那样做： 在此处输入图像描述

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

非常感谢您的帮助。

标签： javaminimum-spanning-treeclrs

解决方案

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

并且事实证明，优先级队列在删除其中一个元素时不会更新其元素。根据 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. b我认为它仍然是一个 MST ，但是有没有办法可以优先考虑访问节点h？即，如果优先级队列中存在关系，则优先考虑具有较低字母数字优先级的键？

推荐阅读