Отладка алгоритма трассировки дерева BFS

Question

Я работаю один в этом проекте и могу использовать другой набор глаз, чтобы посмотреть на это, чтобы увидеть, что я делаю неправильно. Первый цикл работает бесконечно.

public void bfs(String start) 
    { 
     //Initial Case 
     add_queue.add(start); 
     graph.visit(start); 

     Iterator<String> neighbors; 
     String neighbor; 

     while(!add_queue.empty()) 
     { 
      neighbors = graph.neighbors(start); 
      neighbor = neighbors.next(); 
      graph.visit(neighbor); 
      add_queue.add(neighbor); 
      while(neighbors.hasNext()) 
      { 
       neighbor = neighbors.next(); 
       if(!graph.isVisited(neighbor)) //If vertex is not visited it is new and is added to the queue 
       { 
        add_queue.add(neighbor); 
        graph.visit(neighbor); 
       } 

      } 
      start = add_queue.remove(); 
      remove_queue.add(start); //transfers vertex from add_queue to remove queue so that the order that the vertices were traversed is stored in memory  
     } 
    } 

Answer 1

Я думаю, что вы добавляете первую вершину соседей без проверки, если он уже побывал .. здесь:

neighbor = neighbors.next(); <- you get first 
graph.visit(neighbor); <- you visit 
add_queue.add(neighbor); <- you add it without any check 
while(neighbors.hasNext()) 
{ 
    neighbor = neighbors.next(); 
    if(!graph.isVisited(neighbor)) <- you do check for the others 
    { 
    add_queue.add(neighbor); 
    graph.visit(neighbor); 
    } 
} 

Это означает, что вы никогда не пусто, что очереди .. так как она начинается с размером 1 , то вы удаляете 1 элемент на каждой итерации, но вы добавляете по крайней мере 1 элемент (вы никогда не добавляете ни одного).

Answer 2

Что определение add_queue «s из empty()?

Это может быть плохой вопрос присвоения имен, но это звучит как empty()делает что-то, а не просто проверяет, является ли он пустой (который был бы, вероятно, называется isEmpty()).

Кроме того, похоже, что вы всегда добавляете по крайней мере 1 к add_queue в каждом внешнем цикле (прямо перед внутренним while), но только удаляете один элемент из add_queue за итерацию.

Answer 3

Несколько мест для исследования:

1. Проверьте, чтобы убедиться, что graph.isVisited() на самом деле распознавания, когда узел был посещен через graph.visit().
2. Действительно ли graph.neighbor(start) действительно возвращает соседей начала? И не включая начало в этом списке?

Answer 4

Ваш код немного неясен. Что именно возвращает graph.neighbors?

В общем, чтобы сделать BFS, вы хотите добавить детей текущего узла в очередь, а не его соседей. Так как все идет в очередь, это гарантирует, что вы будете посещать каждый узел в дереве в правильном порядке. Предполагая, что это дерево, а не общий граф, это также гарантирует, что вы не посещаете узел более одного раза, позволяя удалить проверки до isVisited.

Итак, выведите следующий узел из очереди, добавьте все его дочерние элементы в очередь, заходите в узел и повторяйте, пока очередь не будет пустой.