Java广度/宽度（BFS）优先搜索实现

最近复习了一下图的搜索算法，用Java实现一下练个手。广度优先算法，又叫宽度优先算法，Breadth-First Search BFS，是在连通图中求两个节点之间最短路径的方法，常用来做一些迷宫求解问题。

迷宫节点定义类：

public class Point{
        int x; //X坐标，Java二维数组的X表示纵坐标
        int y; //Y坐标，Java二位数组的Y表示横坐标
        Point parent; //指向前一个节点的指针，用于最后取出完整的路径

        Point(int x,int y,Point parent){
            this.x = x;
            this.y = y;
            this.parent = parent;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Point)) return false;

            Point point = (Point) o;

            if (x != point.x) return false;
            return y == point.y;
        }

        @Override
        public int hashCode() {
            int result = x;
            result = 31 * result + y;
            return result;
        }
    }

搜索方法实现，核心思想是通过队列来实现节点遍历。每次遍历节点时，将周围的节点加入队列中。

    //用于记录已经遍历过的节点
    private  Map<Integer,List<Integer>> searched = new HashMap<>();
    //广度优先搜索的队列
    private  Queue<Point> queue = new LinkedList<>();

    public void search(int[][] maze,int startx,int starty,int endx,int endy){
        //用于最后存储结果
        List<Point> resList = new ArrayList<>();
        //初始节点
        Point start = new Point(startx,starty,null);
        //最终节点
        Point end = new Point(endx,endy,null);
        queue.offer(start);
        while (!queue.isEmpty()) {
            Point p = queue.poll();

            //找到终点开始回溯路径
            if (p.equals(end)) {
                while (p!= null) {
                    resList.add(p);
                    p = p.parent;
                }
                break;
            }

            int x = p.x;
            int y = p.y;


            //left
            if (y - 1 >= 0 && maze[x][y - 1] != 1) {
                check(x, y - 1, p);
            }

            //bottom
            if (x + 1 < maze.length && maze[x + 1][y] != 1) {
                check(x + 1, y, p);
            }

            //right
            if (y + 1 < maze[x].length && maze[x][y + 1] != 1) {
                check(x, y + 1, p);
            }

            //top
            if (x - 1 >= 0 && maze[x - 1][y] != 1) {
                check(x - 1, y, p);
            }
        }

        for (int i = resList.size()-1;i>=0;i--) {
            System.out.println("["+resList.get(i).x+","+resList.get(i).y+"]");
        }
    }

    private void check(int x, int y, Point p){
        if(searched.get(x)!=null){
            List<Integer> arrayList = searched.get(x);
            //如果已经遍历过，不再重复遍历
            if (!arrayList.contains(y)){
                arrayList.add(y);
                queue.offer(new Point(x,y,p));
            }
        }else {
            List<Integer> arrayList = new ArrayList<>();
            arrayList.add(y);
            searched.put(x,arrayList);
            queue.offer(new Point(x,y,p));
        }
    }

最后附上测试方法，0表示可以走的点，1表示不可走的边界

    @Test
    public void testSearch() throws Exception {
        int[][] maze = {
                {0,1,0,0,0},
                {0,1,0,1,0},
                {0,0,0,0,0},
                {0,1,1,1,0},
                {0,0,0,1,0}
        };

        MazeSearch mazeSearch = new MazeSearch();
        mazeSearch.search(maze,0,0,4,4);
    }


    @Test
    public void testSearch2() throws Exception {
        int[][] maze = {
                {0,1,0,0,0},
                {0,1,0,1,0},
                {0,0,0,1,0},
                {0,1,1,1,0},
                {0,0,0,1,0}
        };

        MazeSearch mazeSearch = new MazeSearch();
        mazeSearch.search(maze,0,0,4,4);
    }
    
    @Test
    public void testSearch3() throws Exception {
        int[][] maze = {
                {0,1,0,0,0},
                {0,1,0,1,0},
                {0,0,0,1,0},
                {0,1,1,1,0},
                {0,0,0,1,0}
        };

        MazeSearch mazeSearch = new MazeSearch();
        mazeSearch.search(maze,0,4,4,2);
    }