php小编草莓广度优先搜索算法是一种常用的图遍历算法，但在某些情况下，它可能会出现错误的结果。广度优先搜索算法通常用于解决图的最短路径问题，其核心思想是从起始节点开始，逐层遍历图中的节点，直到找到目标节点或遍历完所有节点。然而，当图中存在环路或存在多个目标节点时，广度优先搜索算法可能无法得到正确的结果。因此，在使用广度优先搜索算法时，需要注意其局限性，并结合具体问题场景选择合适的算法。
问题内容
昨天我问了一个关于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
那么代码在哪里呢？
解决方法
您没有正确处理职位。此代码变异 i：
int[] c = i;
c[0]++;
您似乎认为 c 是数组的副本，但事实并非如此。它仅引用 i 引用的数组，因此当您执行 c[0]++ 时，该单个数组现在具有该递增值。下次您应用此类代码时（在接下来的 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});
} 
