Breadth-first search algorithm is wrong

php editor's strawberry breadth-first search algorithm is a commonly used graph traversal algorithm, but in some cases, it may produce wrong results. The breadth-first search algorithm is usually used to solve the shortest path problem of graphs. Its core idea is to start from the starting node and traverse the nodes in the graph layer by layer until the target node is found or all nodes are traversed. However, the breadth-first search algorithm may not get correct results when there are cycles in the graph or when there are multiple target nodes. Therefore, when using the breadth-first search algorithm, you need to pay attention to its limitations and select an appropriate algorithm based on specific problem scenarios.

Question content

Yesterday I asked a question about dfs. Today I'm trying to implement bfs.

The .java classes not given in this thread are taken from the previous question.

I wrote 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);
                }
            }
        }
    }
}

I added the following to the main.java class:

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 initially, so we can skip them.

else
{
    grid[i[0]][i[1]].setisvisited(true);

I set the node with position=visited so I don't need to check it again.

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);
}

Finally, we delete the visited nodes:

arraydeque.remove(i);

What I get in the output is:

0
0
0
0
0

So where is the code?

Solution

You are not handling positions correctly. This code mutation i:

int[] c = i;
    c[0]++;

You seem to think that c is a copy of the array, but this is not the case. It only references the array referenced by i, so when you do c[0] that single array now has that incremented value. The next time you apply such code (in one of the next if blocks), you won't start from the original position, but from the already mutated i, So your "steps" go astray.

Honestly, I already pointed out in my answer to your previous question that the idea of ​​using array type positions resulted in less elegant code, and now we see how easy it is to introduce bugs with it.

If you use such an array, you must actually construct the new array and copy the contents of the original array.

The following is a correction to this part of the 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});
        }

The above is the detailed content of Breadth-first search algorithm is wrong. For more information, please follow other related articles on the PHP Chinese website!