I am trying to use the breadth first search algorithm using Java. Considering the 10x10 grid I am trying to find the last cell 9x9 (The grid starts from 0,0 ). By the time when it reaches the 9x9 it has traversed all the cells in the grid. I heard like the BFS will give me the shortest path. But actually it has given me the longest path.
- Could you please tell me if this is the expected behaviour ?
- If this is how the BFS will work then what is the best way to get the shortest route to the 9x9 the cell ?
Please advice.
Edit-- I have used this logic and completed my game. If you want to refer please check https://play.google.com/store/apps/details?id=com.game.puzzle.game.ballmania.android
Code
package com.example.game.bfs.alogrithm;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class BFS {
static class Cell {
private int x;
private int y;
private String value;
private boolean visitStatus;
public Cell(int x, int y, String value,boolean visitStatus) {
this.x = x;
this.y = y;
this.value = value;
this.visitStatus=visitStatus;
}
}
private Cell[][] board;
private List<Cell> visited = new ArrayList<Cell>();
private boolean testDone;
public void setBoard(Cell[][] board) {
this.board = board;
}
public Cell getAdjacentUnvisitedCell(Cell cell)
{
int moves[][] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };
for (int n = 0; n < 4 /* moves.length */; ++n) {
int ti = cell.x + moves[n][0];
int tj = cell.y + moves[n][1];
// System.out.println("ti,tj" + ti +"," + tj );
if (ti >= 0 && ti < board.length && tj >= 0 && tj < board[0].length) {
// System.out.println("getAdjacentUnvisitedCell : " + "[" + board[ti][tj].x + "," + board[ti][tj].y + "]" );
// System.out.println("getAdjacentUnvisitedCell : board[ti][tj].visitStatus " + board[ti][tj].visitStatus );
if(!board[ti][tj].visitStatus) {
return board[ti][tj];
}
}
}
return null;
}
public void BFSearch(Cell start, Cell end) {
// BFS uses Queue data structure
Queue<Cell> q = new LinkedList<Cell>();
q.add(start);
visited.add(start);
board[start.x][start.y].visitStatus = true;
//printNode(start);
while( !q.isEmpty() )
{
Cell c;
c = q.peek();
Cell unVisitedadjCell = getAdjacentUnvisitedCell(c);
if(!testDone){
testDone=true;
}
if ( unVisitedadjCell != null )
{ visited.add(unVisitedadjCell);
board[unVisitedadjCell.x][unVisitedadjCell.y].visitStatus = true;
printNode(unVisitedadjCell,c);
q.add(unVisitedadjCell);
}
else
{
q.remove();
}
}
visited.clear(); //Clear visited property of nodes
}
private void printNode(Cell c,Cell node) {
System.out.println("For Node " + node.x +"," + node.y + ", " + "Just Visited : " + "[" + c.x + "," + c.y + "]" );
}
public static void main(String[] args) {
Cell[][] cells = new Cell[10][10];
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
cells[i][j] = new Cell(i, j, "defaultvalue",false);
}
}
BFS board = new BFS();
board.setBoard(cells);
board.BFSearch(cells[0][0], cells[1][4]);
}
}
}
Log :
For Node 0,0, Just Visited : [1,0]
For Node 0,0, Just Visited : [0,1]
For Node 1,0, Just Visited : [2,0]
For Node 1,0, Just Visited : [1,1]
For Node 0,1, Just Visited : [0,2]
For Node 2,0, Just Visited : [3,0]
For Node 2,0, Just Visited : [2,1]
For Node 1,1, Just Visited : [1,2]
For Node 0,2, Just Visited : [0,3]
For Node 3,0, Just Visited : [4,0]
For Node 3,0, Just Visited : [3,1]
For Node 2,1, Just Visited : [2,2]
For Node 1,2, Just Visited : [1,3]
For Node 0,3, Just Visited : [0,4]
For Node 4,0, Just Visited : [5,0]
For Node 4,0, Just Visited : [4,1]
For Node 3,1, Just Visited : [3,2]
For Node 2,2, Just Visited : [2,3]
For Node 1,3, Just Visited : [1,4]
For Node 0,4, Just Visited : [0,5]
For Node 5,0, Just Visited : [6,0]
For Node 5,0, Just Visited : [5,1]
For Node 4,1, Just Visited : [4,2]
For Node 3,2, Just Visited : [3,3]
For Node 2,3, Just Visited : [2,4]
For Node 1,4, Just Visited : [1,5]
For Node 0,5, Just Visited : [0,6]
For Node 6,0, Just Visited : [7,0]
For Node 6,0, Just Visited : [6,1]
For Node 5,1, Just Visited : [5,2]
For Node 4,2, Just Visited : [4,3]
For Node 3,3, Just Visited : [3,4]
For Node 2,4, Just Visited : [2,5]
For Node 1,5, Just Visited : [1,6]
For Node 0,6, Just Visited : [0,7]
For Node 7,0, Just Visited : [8,0]
For Node 7,0, Just Visited : [7,1]
For Node 6,1, Just Visited : [6,2]
For Node 5,2, Just Visited : [5,3]
For Node 4,3, Just Visited : [4,4]
For Node 3,4, Just Visited : [3,5]
For Node 2,5, Just Visited : [2,6]
For Node 1,6, Just Visited : [1,7]
For Node 0,7, Just Visited : [0,8]
For Node 8,0, Just Visited : [9,0]
For Node 8,0, Just Visited : [8,1]
For Node 7,1, Just Visited : [7,2]
For Node 6,2, Just Visited : [6,3]
For Node 5,3, Just Visited : [5,4]
For Node 4,4, Just Visited : [4,5]
For Node 3,5, Just Visited : [3,6]
For Node 2,6, Just Visited : [2,7]
For Node 1,7, Just Visited : [1,8]
For Node 0,8, Just Visited : [0,9]
For Node 9,0, Just Visited : [9,1]
For Node 8,1, Just Visited : [8,2]
For Node 7,2, Just Visited : [7,3]
For Node 6,3, Just Visited : [6,4]
For Node 5,4, Just Visited : [5,5]
For Node 4,5, Just Visited : [4,6]
For Node 3,6, Just Visited : [3,7]
For Node 2,7, Just Visited : [2,8]
For Node 1,8, Just Visited : [1,9]
For Node 9,1, Just Visited : [9,2]
For Node 8,2, Just Visited : [8,3]
For Node 7,3, Just Visited : [7,4]
For Node 6,4, Just Visited : [6,5]
For Node 5,5, Just Visited : [5,6]
For Node 4,6, Just Visited : [4,7]
For Node 3,7, Just Visited : [3,8]
For Node 2,8, Just Visited : [2,9]
For Node 9,2, Just Visited : [9,3]
For Node 8,3, Just Visited : [8,4]
For Node 7,4, Just Visited : [7,5]
For Node 6,5, Just Visited : [6,6]
For Node 5,6, Just Visited : [5,7]
For Node 4,7, Just Visited : [4,8]
For Node 3,8, Just Visited : [3,9]
For Node 9,3, Just Visited : [9,4]
For Node 8,4, Just Visited : [8,5]
For Node 7,5, Just Visited : [7,6]
For Node 6,6, Just Visited : [6,7]
For Node 5,7, Just Visited : [5,8]
For Node 4,8, Just Visited : [4,9]
For Node 9,4, Just Visited : [9,5]
For Node 8,5, Just Visited : [8,6]
For Node 7,6, Just Visited : [7,7]
For Node 6,7, Just Visited : [6,8]
For Node 5,8, Just Visited : [5,9]
For Node 9,5, Just Visited : [9,6]
For Node 8,6, Just Visited : [8,7]
For Node 7,7, Just Visited : [7,8]
For Node 6,8, Just Visited : [6,9]
For Node 9,6, Just Visited : [9,7]
For Node 8,7, Just Visited : [8,8]
For Node 7,8, Just Visited : [7,9]
For Node 9,7, Just Visited : [9,8]
For Node 8,8, Just Visited : [8,9]
For Node 9,8, Just Visited : [9,9]
The pattern in which the cells are visited.
