Yesterday I asked a question on the DFS. Today I am trying to implement the BFS.
The .java classes not given out in this thread are taken from the previous question.
I have written this class:
BreadthFirstSearch.java
import java.util.ArrayDeque;
import java.lang.System;
public class BreadthFirstSearch extends SearchAlgorithm{
public BreadthFirstSearch(int gridSize)
{
super(gridSize);
}
public void calc(int[]pos)
{
ArrayDeque<int[]>arrayDeque = new ArrayDeque<>();
arrayDeque.add(pos);
while(!arrayDeque.isEmpty())
{
for(int[]i:arrayDeque) {
System.out.println(grid[i[0]][i[1]].getPosition());
if (grid[i[0]][i[1]].getIsExit()) {
System.out.println("Path been found!");
arrayDeque.remove(i);
} else if (grid[i[0]][i[1]].getType() == 1) {
System.out.println("Path been blocked!");
arrayDeque.remove(i);
} else if (grid[i[0]][i[1]].getIsVisited()) {
arrayDeque.remove(i);
}
else
{
grid[i[0]][i[1]].setIsVisited(true);
if (i[0] < gridLength - 1) {
int[] c = i;
c[0]++;
arrayDeque.add(c);
}
if (i[0] > 0) {
int[] d = i;
d[0]--;
arrayDeque.add(d);
}
if (i[1] < gridLength - 1) {
int[] e = i;
e[1]++;
arrayDeque.add(e);
}
if (i[1] > 0) {
int[] f = i;
f[1]--;
arrayDeque.add(f);
}
arrayDeque.remove(i);
}
}
}
}
}
and I have added in the Main.java class this:
BreadthFirstSearch bfs = new BreadthFirstSearch(9);
bfs.print();
bfs.calc(pos);
For the constructor of BreadthFirstSearch.java I get this matrix:
Position:0 Type:0 Position:1 Type:0 Position:2 Type:1
Position:3 Type:0 Position:4 Type:1 Position:5 Type:1
Position:6 Type:1 Position:7 Type:0 Position:8 Type:0
while(!arrayDeque.isEmpty())
{
for(int[]i:arrayDeque) {
System.out.println(grid[i[0]][i[1]].getPosition());
if (grid[i[0]][i[1]].getIsExit()) {
System.out.println("Path been found!");
arrayDeque.remove(i);
} else if (grid[i[0]][i[1]].getType() == 1) {
System.out.println("Path been blocked!");
arrayDeque.remove(i);
} else if (grid[i[0]][i[1]].getIsVisited()) {
arrayDeque.remove(i);
}
none of these conditions are true in the beginning so we can skip them.
else
{
grid[i[0]][i[1]].setIsVisited(true);
I set the node with position = visited, so I don't get to check it out again.
Out of these conditions only (1) and (3) are true, so we add 2 int[] arrays to the deque:
if (i[0] < gridLength - 1) {
int[] c = i;
c[0]++;
arrayDeque.add(c);
}
if (i[0] > 0) {
int[] d = i;
d[0]--;
arrayDeque.add(d);
}
if (i[1] < gridLength - 1) {
int[] e = i;
e[1]++;
arrayDeque.add(e);
}
if (i[1] > 0) {
int[] f = i;
f[1]--;
arrayDeque.add(f);
}
Lastly, we remove the visited node:
arrayDeque.remove(i);
What I get in the output is:
0
0
0
0
0
So where is the code off?
Your are not dealing correctly with the positions. This code mutates i:
int[] c = i;
c[0]++;
You seem to think that c is a copy of the array, but it is not. It merely references the array that i references, and so when you do c[0]++, that single array now has that incremented value. The next time you apply this kind of code (in one of the next if blocks), you'll not start with the original position, but with the already mutated i, and so your "steps" are going astray.
Honestly, I had already indicated in my answer to your previous question that working with the idea of array-type positions leads to less elegant code, and now we see how easy it is to introduce bugs with it.
If you work with such arrays, you'll have to really construct new arrays and copy the contents of the original array.
Here is the correction of that part of your code:
if (i[0] < gridLength - 1) {
arrayDeque.add(new int[] {i[0]+1, i[1]});
}
if (i[0] > 0) {
arrayDeque.add(new int[] {i[0]-1, i[1]});
}
if (i[1] < gridLength - 1) {
arrayDeque.add(new int[] {i[0], i[1]+1});
}
if (i[1] > 0) {
arrayDeque.add(new int[] {i[0], i[1]-1});
}