Отладка алгоритма обхода дерева 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

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

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

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

Answer 3

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

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

Answer 4

Каково add_queue определение empty()?

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

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