1

我正在尝试使用优先级队列来实现 prim 的算法。当我调用 offer() 方法时，它给了我一个类转换异常，说顶点不能转换为可比较的。有解决方法吗？ 

public static Collection<Edge> prims(Graph g, int start) {
            ArrayList<Edge> mst = new ArrayList<Edge>();
            PriorityQueue<Vertex> vertices = new PriorityQueue<Vertex>();
            Vertex startVertex;

        for (Vertex vertex : g.getVertices()) {
            vertices.offer(vertex);
            if (vertex.getId() == start) {
                startVertex = vertex;
            }
        }

        if (!mst.isEmpty()) {
            return mst;
        }

        return null;
    }
}
4

3 回答 3

3

Prims 算法使用边缘的权重来确定最佳路径。将顶点发布到PriorityQueue将不起作用。

我猜你的Edge课程将Comparable通过比较它们的长度来实现。

于 2014-11-26T12:20:52.463 回答
0

是的：你需要你的Vertex方法来实现Comparable<Vertex>.

JavaPriorityQueue是堆的实现，它具有日志时间插入和日志时间删除最小元素。但是为了让它有意义，你需要有一个minimum的概念；这意味着您需要放入 a PriorityQueueto be的任何内容Comparable，以便可以比较堆中的两个元素。

非Comparable元素可以插入 a的原因PriorityQueue是你也可以Comparator在构造函数中指定 a，而不是使用Comparable元素。因此，作为替代方案，您可以保留您的Vertex类，但使用适当的构造函数（这也需要您指定初始容量）：

PriorityQueue<Vertex> vertices = new PriorityQueue<Vertex>(11,
    new Comparator<Vertex>() {
        //implement .compare() and .equals()
    });
于 2014-11-26T12:19:18.613 回答
0

解决方案是让您的Vertex类实现Comparable，或者Comparator在构造它时向优先级队列提供一个。Java 集合框架需要一种方法来比较您的顶点（毕竟您将它们放入优先级队列中，而优先级意味着存在某些排序的必要性）。

于 2014-11-26T12:19:21.477 回答