Бесконечный цикл шириной первого поиска - PullRequest
Новая
       7

Бесконечный цикл шириной первого поиска

0 голосов
/ 15 января 2019

Я пытался реализовать поиск в ширину, но я считаю, что застрял в бесконечном цикле 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;
}

Любая помощь приветствуется!

Спасибо.

РЕДАКТИРОВАТЬ: обновленный код по-прежнему бесконечный цикл.

Ответы [ 2 ]

0 голосов
/ 15 января 2019

Какой тип узла T здесь? Правильно ли реализованы equals() и hashcode()? Потому что в противном случае проверка ключа содержащихся в списке элементов не удастся. Поэтому всегда будем добавлять узлы в Queue. Вы можете выполнить некоторую простую отладку, если очередь обновляется должным образом.

0 голосов
/ 15 января 2019

Заменить строку 

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

от 

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

Метод contains принимает Object в качестве параметра, поэтому он хорошо компилируется, но вы должны указать объект типа T. Обычно, если вы используете IDE, он должен предупредить вас в этой строке.

...