Infinite loop breadth first search

Question

I have tried to implement breadth first search but I believe I get stuck in a infinite for loop and I am not sure why. My method is below:

public ArrayList<T> performBreadthFirstSearchUndirectedNonWeighted(UndirectedNonWeightedGraph<T> graph, T startingVertex){

    if (!graph.containsVertex(startingVertex)) {
        throw new IllegalArgumentException("Vertex doesn't exist.");
    }
    T currentVertex;
    ArrayList<T> traversalOrder = new ArrayList<T>();
    ArrayList<T> visitedVertices = new ArrayList<T>();
    LinkedList<T> queue = new LinkedList<T>(); 

     visitedVertices.add(startingVertex);
     queue.add(startingVertex);

     while (queue.size() != 0) {
         currentVertex = queue.poll();
         traversalOrder.add(currentVertex);

         Iterator<Vertex<T>> i = graph.getNeighbours(currentVertex).iterator(); 

         while (i.hasNext()) { 
             Vertex<T> n = i.next(); 
                if (!visitedVertices.contains(graph.returnVertex(n.getElement()))) { 
                    visitedVertices.add(n.getElement());
                    queue.add(n.getElement()); 
                } 
            } 
     }
    return traversalOrder;
}

Any help is appreciated!

Thank you.

EDIT: Updated code still infinite loop.

Hi @rustyx nice find on the queue.add() line i didnt see that, however it seems to be in a infinite loop still. I updated the code in the question. — Jaman, Jan 15 '19 at 14:11
@Ricola it takes a element and returns a Vertex object with that element. — Jaman, Jan 15 '19 at 14:12
You call `contains` with `graph.returnVertex(n.getElement())` but add `n.getElement()`. You have to add the same objects for which you do the `contains` check. — Ricola, Jan 15 '19 at 14:13
By the way, I think a [debugger](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) could help you there — Ricola, Jan 15 '19 at 14:14

score 3 · Accepted Answer · answered Jan 15 '19 at 14:16

Replace the line

if (!visitedVertices.contains(graph.returnVertex(n.getElement())))

by

if (!visitedVertices.contains(n.getElement()))

The method contains accept an Object as a parameter so it compiles fine but you have to give a object of type T. Normally if you are using an IDE, it should warn you on this line.

score 0 · Answer 2 · answered Jan 15 '19 at 14:24

What is the type of Node T here? Does it implement equals() and hashcode() properly? Because the key checking of containing elements in the list will fail otherwise. Therefore, will always keep adding nodes to the Queue. You can do some simple debugging if the Queue is getting updated as expected.

Infinite loop breadth first search

2 Answers2