Debugging BFS tree travesal algorithm

Question

I'm working alone on this project and could use another set of eyes to look at this to see what I am doing wrong. The first loop runs infinitely.

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

What's add_queue's definition of empty()?

It could be a bad naming issue, but it sounds like empty() does something, not just checks whether it is empty (which would be probably called isEmpty()).

Also, it looks like you always add at least 1 to add_queue in each outer loop (right before the inner while), but only remove one item from add_queue per iteration.

Answer 2

I think you are adding the first vertex of neighbours without checking if it's already visited.. here:

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);
  }
}

This means that you will never empty that queue.. since it starts with a size of 1, then you remove 1 element on each iteration but you add at least 1 element (you never add noone).

Answer 3

A few places to investigate:

1. Check to make sure that graph.isVisited() is actually recognizing when a node has been visited via graph.visit().
2. Is graph.neighbor(start) truly returning start's neighbors? And not including start in this list?

Answer 4

Your code is a little unclear. What exactly does graph.neighbors return?

In general to do a BFS you want to add the children of the current node to the queue, not the neighbors of it. Since it's all going into a queue this will ensure that you visit each node in the tree in the correct order. Assuming that it's a tree and not a general graph, this will also ensure that you don't visit a node more than once, allowing you to remove the checks to isVisited.

So, get the next node out of the queue, add all of it's children to the queue, visit the node, and repeat, until the queue is empty.