java - 调试 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定义是empty()什么？

这可能是一个糟糕的命名问题，但听起来像是empty() 在做某事，而不仅仅是检查它是否为空（可能会被称为isEmpty()）。

此外，看起来您总是在每个外部循环中（就在内部 while 之前）向 add_queue 添加至少 1，但每次迭代只从 add_queue 中删除一项。

Answer 3

几个地方可以调查：

1. 检查以确保它graph.isVisited()实际上正在识别何时通过 访问节点graph.visit()。
2. 真的是graph.neighbor(start)回归起点的邻居吗？并且不包括此列表中的开始？

Answer 4

你的代码有点不清楚。究竟graph.neighbors返回什么？

通常，要执行 BFS，您希望将当前节点的子节点添加到队列中，而不是它的邻居。由于所有内容都进入队列，这将确保您以正确的顺序访问树中的每个节点。假设它是一棵树而不是一般图，这也将确保您不会多次访问一个节点，从而允许您删除对isVisited.

因此，从队列中取出下一个节点，将其所有子节点添加到队列中，访问该节点，然后重复，直到队列为空。