Prim在Java中的算法实现

Question

我正在尝试在Java中实现Prim的算法，使用我的图形HashMap + LinkedList和一个包含连接顶点和权重的类Edge：

adjacencyList = new HashMap<T, LinkedList<Edge<T>>>();

我的想法是，从一个给定的顶点开始： 1(将所有顶点保存到 LinkedList 中，以便我可以在每次查看它们时删除它们 2(将路径保存到另一个链接列表中，以便我可以进行最终的MST 3(使用优先级队列查找最小权重

最后，我需要MST，边缘数量和总重量。 我对如何返回 MST 感到非常困惑，我的代码上几乎没有错误，我不知道如何修复它们！

首先，我收到此错误：

Prim.java:21: error: no suitable method found for addAll(LinkedList<Edge<T>>)
unvisited.addAll(graph.getVertices());
^
method Collection.addAll(Collection<? extends T>) is not applicable
(argument mismatch; LinkedList<Edge<T>> cannot be converted to Collection<? extends T>)
method List.addAll(Collection<? extends T>) is not applicable
(argument mismatch; LinkedList<Edge<T>> cannot be converted to Collection<? extends T>)
method AbstractCollection.addAll(Collection<? extends T>) is not applicable
(argument mismatch; LinkedList<Edge<T>> cannot be converted to Collection<? extends T>)
method LinkedList.addAll(Collection<? extends T>) is not applicable
(argument mismatch; LinkedList<Edge<T>> cannot be converted to Collection<? extends T>)
where T is a type-variable: T extends Comparable<T> declared in class Prim

似乎问题出在我的getVertices((方法(返回图形的所有顶点(中，因为它返回了一个Set<T>;我尝试使用 addAll 将所有内容放入 LinkedList 中，并返回此 LinkedList，但它给了我相同的错误。我做错了什么？

public class Graph<T extends Comparable<T>> {
.
.
public Set<T> getVertices() {
if (adjacencyList.isEmpty()) {
System.out.println("Error message.n");
return null;
} else
return adjacencyList.keySet();
}
}

第二个错误是：

Prim.java:28: error: incompatible types: T cannot be converted to Edge<T>
for (Edge<T> edge : graph.getAdjacentVertices(source)) {
^
where T is a type-variable:
T extends Comparable<T> declared in class Prim
Note: Some messages have been simplified; recompile with -Xdiags:verbose to get full output

我可以通过将Edge<T>转换为source来修复它，但我认为这根本没有任何意义，因为这个想法是我给出一个可以包含任何类型的顶点，而不仅仅是 Edge。

普里姆的：

public class Prim<T extends Comparable<T>> {
public <SHOULD I RETURN graph ?> minimumSpanningTree(Graph<Edge<T>> graph, T vertex) {
//ArgumentException
double weight = 0;
T source = vertex;
LinkedList<T> vertexSet = new LinkedList<>();
LinkedList<Edge<T>> path = new LinkedList<>();
vertexSet.addAll(graph.getVertices()); //unvisited ERROR HERE
vertexSet.remove(source);
double numberOfVertices = graph.getVertices().size();
PriorityQueue<Edge<T>> priorityQueue = new PriorityQueue<>();
while (!vertexSet.isEmpty()) {
for (Edge<T> edge : graph.getAdjacentVertices(source)) {//ERROR
if (vertexSet.contains(edge.getDestination())) 
priorityQueue.insert(edge);
}
Edge<T> minWeight = priorityQueue.extractMin();
weight += minWeight.getWeight();
path.add(HERE I SHOULD PUT MST PATH BUT I DON'T KNOW HOW!!);
source = minWeight.getDestination();
vertexSet.remove(source);
}
return <graph??>;
}
}

正如我之前所说，我不知道我是否应该返回一个图形作为 MST(也许是我作为删除最昂贵的边缘的输入给出的图表(或称为 LinkedList 的路径，它以最低权重保存路径。 我也不知道如何在 MST 中找到边缘的数量;我是否应该为每个顶点(我的 HashMap 的键集(找到 LinkedList 的大小(这是它的值(并将它们全部相加？

编辑：获取相邻顶点方法

public LinkedList<T> getAdjacentVertices(T vertex) {
if (adjacencyList.isEmpty() || adjacencyList.containsKey(vertex) == false) {
System.out.println("Error msg.n");
return null;
} else {
LinkedList<T> allAdjacents = new LinkedList<>();
for (Edge<T> edge : adjacencyList.get(vertex)) {
allAdjacents.add(edge.getDestination());
}
return allAdjacents;
}
}

Answer 1

1(我想错误不在于getVertices()，而在于您的Graph在Edge<T>上被定义为通用而不是T。Graph<T>被实例化为Graph<Edge<T1>>，因此作为返回值Set<T>被固定为Set<Edge<T1>>。

我建议你将Graph定义为Graph<Edge<T>>，并从那里重构图的逻辑，或者将IEdge<T>定义为Edge<T>的超接口，并将图重新定义为Graph<? extends IEdge<T>>。

例如(蒙上眼睛(：

public class Graph<T> {
Map<T, Edge<T>> adjacencyList;
public Set<T> getVertices() {
if (adjacencyList.isEmpty()) {
System.out.println("Error message.n");
return null;
} else {
return adjacencyList.keySet();
}
}
}
Graph<Point> p;
List<Point> points = new LinkedList<>();
points.addAll(p.getVertices());

2( 1 的变体。在本例中，您返回的是List<T>但因为您骑自行车时：

for (Edge<T> edge : graph.getAdjacentVertices(source))

getAdjacentVertices的返回值应为Enumerable<Edge<T>>，而您提供Enumerable<T>。您可能希望在getAdjacentVertices实现中返回如下内容：

LinkedList<Edge<T>> allAdjacents = new LinkedList<>();
for (Edge<T> edge : adjacencyList.get(vertex)) {
allAdjacents.add(edge);
}
return allAdjacents;