java无限循环宽度优先搜索

Question

我曾尝试实现广度优先搜索，但我相信我陷入了无限的for循环，我不知道为什么。我的方法如下：

public ArrayList<T> performBreadthFirstSearchUndirectedNonWeighted(UndirectedNonWeightedGraph<T> graph, T startingVertex){

    if (!graph.containsVertex(startingVertex)) {
        throw new IllegalArgumentException("Vertex doesn't exist.");
    }
    T currentVertex;
    ArrayList<T> traversalOrder = new ArrayList<T>();
    ArrayList<T> visitedVertices = new ArrayList<T>();
    LinkedList<T> queue = new LinkedList<T>(); 

     visitedVertices.add(startingVertex);
     queue.add(startingVertex);

     while (queue.size() != 0) {
         currentVertex = queue.poll();
         traversalOrder.add(currentVertex);

         Iterator<Vertex<T>> i = graph.getNeighbours(currentVertex).iterator(); 

         while (i.hasNext()) { 
             Vertex<T> n = i.next(); 
                if (!visitedVertices.contains(graph.returnVertex(n.getElement()))) { 
                    visitedVertices.add(n.getElement());
                    queue.add(n.getElement()); 
                } 
            } 
     }
    return traversalOrder;
}

感谢您的帮助

多谢各位

编辑：更新的代码仍然是无限循环

Answer 1

这里的节点T是什么类型？它是否正确地实现了equals()和hashcode()？否则，对列表中包含的元素的键检查将失败。因此，将始终向Queue添加节点。如果队列按预期更新，则可以执行一些简单的调试

Answer 2

更换线路

if (!visitedVertices.contains(graph.returnVertex(n.getElement())))

借

if (!visitedVertices.contains(n.getElement()))

方法contains接受一个Object作为参数，因此它可以很好地编译，但是您必须给出一个类型为T的对象。通常，如果您使用的是IDE，它会在这一行警告您