CODEWITHSUNDEEP
javabreadth-first-search
Jaman
Jaman

Reputation: 125

Infinite loop breadth first search

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.

Upvotes: 2

Views: 409

Answers (2)

shakhawat
shakhawat

Reputation: 2727

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.

Upvotes: 0

Ricola
Ricola

Reputation: 2922

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.

Upvotes: 3

Related Questions