Amine Amine - 2 months ago 17
Java Question

BFS not returning a path

I am trying to implement BFS on a 2d array given the start point and end point. I tried giving my function two points on the grid, but it returns an empty array meaning that there is no path.

Can someone please point where am I going wrong and if possible help me correct my error? Thanks.

public Point[] bfs2(Point start, Point end) {
boolean[][] visited = new boolean[50][50];
for (int i = 0; i < visited.length; i++)
for(int j = 0; j < visited.length; j++)
visited[i][j] = false;

visited[start.getX()][start.getY()] = true;
LinkedList<Point> path = new LinkedList<>();
Queue<Point> q = new LinkedList<>();
q.add(start);

while (!q.isEmpty()) {
Point next = q.remove(); //i think the error is here
Point[] neighbours = next.getNeighbours();
path.add(next);

if (next.getX() == end.getX() && next.getY() == end.getY())
break;
else if (!visited[next.getX()][next.getY()]) {
for (Point neighbour : neighbours) {
if (!visited[neighbour.getX()][neighbour.getY()]) {
q.add(neighbour);
}

visited[neighbour.getX()][neighbour.getY()] = true;
}
}
}

Point current = path.removeLast();
ArrayList<Point> v = new ArrayList<>();
while (current.getX() != start.getX() || current.getY() != start.getY()) {
v.add(current);
current = path.removeLast();
}

return v.toArray(new Point[v.size()]);
}


EDIT:

Point current=q.peek();
ArrayList<Point> v=new ArrayList<>();
if(start.getX()==end.getX() && start.getY()==end.getY()) return new Point[0];
while(current.getX()!=start.getX() || current.getY()!=start.getY()){
v.add(current);
current=current.parent;
}
return v.toArray(new Point[v.size()]);

Answer

The first issue is that you're adding all the elements you remove from the queue to the path (I'm referring to the line containing path.add(next);).

Instead, you should keep track of the parent node from which you visited each node. When you find the end node, you can trace back your steps to the start node.

If you have exhausted all the nodes and you still haven't found the end node, you can then return an empty list.

Let me know if you need an MCV example, and I'll add it.

Later Edit:

You need to add a Point parent field to your class, like this:

class Point {
    int x;
    int y;
    Point parent; // reference to the Point from which this Point was visited

    // constructors, getters, setters, etc.
}

Then you can change your BFS implementation to also set the parent for the current node when iterating through its neighbors. You must change the loop to something like this:

        for (Point neighbour : neighbours) {
            if (!visited[neighbour.getX()][neighbour.getY()]) {
                q.add(neighbour);
                visited[neighbour.getX()][neighbour.getY()] = true;
                neighbour.parent = next;
            }
        }
Comments