广度优先搜索算法是错误的

Question

昨天我问了一个关于DFS的问题。今天我正在尝试实现 BFS。

本线程中未给出的 .java 类取自上一个问题。

我写了这门课：

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

我在 Main.java 类中添加了以下内容：

BreadthFirstSearch bfs = new BreadthFirstSearch(9);
bfs.print();
bfs.calc(pos);

对于

BreadthFirstSearch.java

的构造函数，我得到这个矩阵：

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

这些条件一开始都不成立，所以我们可以跳过它们。

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

我将节点设置为position=visited，所以我不需要再次检查它。

在这些条件中，只有 (1) 和 (3) 为真，因此我们向双端队列添加 2 个 int[] 数组：

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

我在输出中得到的是：

0
0
0
0
0

那么代码在哪里呢？

Answer 1

您没有正确处理职位。这段代码发生了变化

i

：

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

您似乎认为

c

是 array 的 copy，但事实并非如此。它仅引用

i

引用的数组，因此当您执行

c[0]++

时，该 single 数组现在具有递增的值。下次应用此类代码时（在接下来的

if

块之一中），您将不会从原始位置开始，而是从已经变异的

i

开始，因此您的“步骤”会误入歧途。

老实说，我已经在对你之前问题的回答中指出，使用数组类型位置的想法会导致代码不太优雅，现在我们看到用它引入错误是多么容易。

如果您使用此类数组，则必须真正构造新数组并复制原始数组的内容。

这是对代码那部分的更正：

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