Breadth First Search（BFS）Java实现异常，输出重复0问题排查

问题背景 #

昨日在Stack Overflow上询问了DFS相关问题，今日尝试实现广度优先搜索（BFS）算法。未给出的Java类取自之前的问题，编写了BreadthFirstSearch.java类并在Main.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

执行代码时，初始条件均不触发，标记节点为已访问后添加相邻节点到队列，但最终输出重复显示0，请问代码哪里存在问题？

相关代码 #

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

问题分析与解决 #

核心问题1：BFS遍历逻辑错误 #

你在while循环里用for(int[]i:arrayDeque)遍历整个队列，这违背了BFS“先进先出、逐个处理队列头部元素”的核心逻辑，会导致队列中的元素被重复遍历处理，直接引发输出重复的问题。

核心问题2：数组引用复用导致数据混乱 #

添加相邻节点时，你直接复用原数组的引用：

int[] c = i;
c[0]++;
arrayDeque.add(c);

这里c只是i的引用，修改c的元素等同于修改原数组i的元素。后续添加的d、e、f也都是同一个数组的引用，最终队列中所有元素指向同一个数组对象，所有节点的位置信息被反复覆盖，表现为输出重复的0。

核心问题3：已访问标记时机错误 #

你在处理节点时才标记为已访问，但此时该节点已经在队列中，容易导致同一节点被多次加入队列，重复处理。正确的做法是节点入队时就标记为已访问。

修复后的代码示例 #

import java.util.ArrayDeque;

public class BreadthFirstSearch extends SearchAlgorithm{

    public BreadthFirstSearch(int gridSize)
    {
        super(gridSize);
    }

    public void calc(int[] pos)
    {
        ArrayDeque<int[]> arrayDeque = new ArrayDeque<>();
        // 入队时立即标记已访问，避免重复入队
        grid[pos[0]][pos[1]].setIsVisited(true);
        arrayDeque.add(pos);
        
        while(!arrayDeque.isEmpty())
        {
            // 从队列头部取出单个元素处理，符合BFS逻辑
            int[] current = arrayDeque.poll();
            int x = current[0];
            int y = current[1];
            
            System.out.println(grid[x][y].getPosition());
            
            if (grid[x][y].getIsExit()) {
                System.out.println("找到路径！");
                return; // 找到出口后直接终止算法
            } else if (grid[x][y].getType() == 1) {
                System.out.println("路径被阻挡！");
                continue;
            }
            
            // 添加相邻节点，创建新数组避免引用复用
            // 向下
            if (x < gridLength - 1) {
                int[] down = new int[]{x + 1, y};
                if (!grid[down[0]][down[1]].getIsVisited()) {
                    grid[down[0]][down[1]].setIsVisited(true);
                    arrayDeque.add(down);
                }
            }
            // 向上
            if (x > 0) {
                int[] up = new int[]{x - 1, y};
                if (!grid[up[0]][up[1]].getIsVisited()) {
                    grid[up[0]][up[1]].setIsVisited(true);
                    arrayDeque.add(up);
                }
            }
            // 向右
            if (y < gridLength - 1) {
                int[] right = new int[]{x, y + 1};
                if (!grid[right[0]][right[1]].getIsVisited()) {
                    grid[right[0]][right[1]].setIsVisited(true);
                    arrayDeque.add(right);
                }
            }
            // 向左
            if (y > 0) {
                int[] left = new int[]{x, y - 1};
                if (!grid[left[0]][left[1]].getIsVisited()) {
                    grid[left[0]][left[1]].setIsVisited(true);
                    arrayDeque.add(left);
                }
            }
        }
        System.out.println("未找到出口路径");
    }
}

修复说明 #

1. 使用poll()方法从队列头部取出单个元素处理，严格遵循BFS的“先进先出”遍历逻辑，避免重复处理元素。
2. 添加相邻节点时创建新的int[]对象，彻底解决数组引用复用导致的位置信息混乱问题。
3. 节点入队时立即标记为已访问，防止同一节点被多次加入队列。
4. 找到出口后直接return终止算法，无需继续无效遍历。

内容的提问来源于stack exchange，提问作者Root Groves