Java实现广度优先遍历的示例详解

什么是广度优先遍历

广度优先遍历（Breadth First Search, BFS）是一种图形的遍历算法，其遍历能力基于层次高效地访问相邻节点，并按顺序访问节点。这种方式即宽度优先，图形遍历的起点为根节点，相关的数据结构是队列。

广度优先遍历的应用

广度优先遍历算法在许多领域都有应用，比如：

• 寻找最短路径
• 二叉树搜索
• 网络路由算法
• 解决 谷仓机器人 题目

广度优先遍历的实现

可以通过迭代方法实现广度优先遍历，采用队列结构进行节点遍历。

例如下面这个二叉树：

    5
  /  \
 4    6
/ \    \

2 3 7

示例1：Java代码示例

import java.util.LinkedList;
import java.util.Queue;

class Node {
    int value;
    Node left;
    Node right;
}

public class BFS {

    public void bfs(Node root) {
        if (root == null)
            return;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        Node node;
        while (!queue.isEmpty()) {
            node = queue.poll();
            System.out.print(node.value + " ");
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }

    public static void main(String[] args) {
        Node root = new Node();
        root.value = 5;
        Node node1 = new Node();
        node1.value = 4;
        Node node2 = new Node();
        node2.value = 6;
        Node node3 = new Node();
        node3.value = 2;
        Node node4 = new Node();
        node4.value = 3;
        Node node5 = new Node();
        node5.value = 7;
        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.right = node5;
        new BFS().bfs(root);
    }
}

输出：

5 4 6 2 3 7

示例2：使用队列实现谷仓机器人题目中的广度优先遍历问题

题目描述：In a RxC matrix, every cell of which is either containing ‘’ or a ‘X’. Given a starting point and a ending point, every cell containing ‘’ can be destroyed by placing a bomb at the cell. Implement an efficient algorithm to destroy all ‘*’ possible cells.

解法：使用队列实现广度优先搜索，每一步把周围为‘’的点加入队列，不断处理，直至队列为空或者所有 '' 都已经小心地处理了。这个题目可以通过广度优先搜索来解决。

Java代码示例：

import java.util.LinkedList;
import java.util.Queue;

public class DestroyAllStars {

    static class Point {
        int x;
        int y;

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

    static char[][] map = {
            {'*', 'X', '*', 'X', '*', '*', 'X'},
            {'*', 'X', '*', 'X', '*', 'X', '*'},
            {'X', '*', '*', '*', '*', '*', 'X'},
            {'*', 'X', '*', 'X', '*', '*', 'X'},
            {'*', '*', '*', '*', '*', 'X', '*'}
    };

    public static void main(String[] args) {
        Queue<Point> queue = new LinkedList<>();
        boolean[][] visited = new boolean.length];
        queue.offer(new Point(0, 0));
        while (!queue.isEmpty()) {
            Point p = queue.poll();
            visited[p.x][p.y] = true;
            for (int i = -1; i <= 1; i++) {
                for (int j = -1; j <= 1; j++) {
                    int x = p.x + i;
                    int y = p.y + j;
                    if (x >= 0 && x < map.length && y >= 0 && y < map[0].length && map[x][y] == '*' && !visited[x][y]) {
                        queue.offer(new Point(x, y));
                        visited[x][y] = true;
                        map[x][y] = 'X';
                    }
                }
            }
        }
        printMap(map);
    }

    private static void printMap(char[][] map) {
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }

}

输出：

X X X X X X X 
X X X X X X X 
X X X X X X X 
X X X X X X X 
X X X X X X X

总结

广度优先遍历是一种基于层级遍历的算法，遍历的起点为根节点，遍历的过程中需要基于队列结构按照先入先出的原则来访问节点。在实际编程中，可以通过队列结构来实现广度优先遍历，其应用场景包括寻找最短路径、二叉树搜索、网络路由算法等。