调试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) 真的返回了 start 的邻居吗？并且不包括此列表中的开始？

Answer 4

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

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

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