BFS 算法在 Java 中的应用

简介

广度优先搜索（Breadth-First Search，简称 BFS）是一种用于遍历或搜索图或树结构的算法。在许多实际问题中，比如寻找最短路径、解决迷宫问题等，BFS 都展现出了强大的性能。本文将深入探讨 BFS 算法在 Java 中的实现、应用场景以及最佳实践。

BFS 基础概念

BFS 从给定的起始顶点开始，以广度逐层的方式遍历图或树的节点。它使用队列（Queue）作为辅助数据结构，先将起始节点放入队列，然后不断从队列中取出节点，访问该节点，并将其未访问过的邻居节点加入队列。这个过程持续进行，直到队列为空。

为什么使用 BFS

寻找最短路径：由于 BFS 是按层次遍历的，所以当找到目标节点时，所经过的路径就是从起始节点到目标节点的最短路径（在无权图中）。
全面搜索：可以保证遍历到所有可达节点，不会遗漏任何节点。

BFS 在 Java 中的使用方法

图的表示

在 Java 中，通常使用邻接表（Adjacency List）来表示图。以下是一个简单的图节点类和图类的实现：

import java.util.ArrayList;
import java.util.List;

// 图节点类
class GraphNode {
    int val;
    List<GraphNode> neighbors;

    GraphNode(int val) {
        this.val = val;
        this.neighbors = new ArrayList<>();
    }
}

// 图类
class Graph {
    private List<GraphNode> nodes;

    Graph() {
        this.nodes = new ArrayList<>();
    }

    void addNode(GraphNode node) {
        nodes.add(node);
    }

    void addEdge(GraphNode from, GraphNode to) {
        from.neighbors.add(to);
        to.neighbors.add(from); // 如果是无向图
    }
}

BFS 实现

下面是使用 Java 实现 BFS 算法的代码示例。假设我们要从一个起始节点开始，遍历整个图，并标记所有访问过的节点。

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

public class BFSExample {
    public static void bfs(GraphNode start) {
        boolean[] visited = new boolean[100]; // 假设节点值范围在 0 - 99
        Queue<GraphNode> queue = new LinkedList<>();

        queue.add(start);
        visited[start.val] = true;

        while (!queue.isEmpty()) {
            GraphNode current = queue.poll();
            System.out.println("Visited node: " + current.val);

            for (GraphNode neighbor : current.neighbors) {
                if (!visited[neighbor.val]) {
                    queue.add(neighbor);
                    visited[neighbor.val] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        // 创建图
        Graph graph = new Graph();
        GraphNode node1 = new GraphNode(1);
        GraphNode node2 = new GraphNode(2);
        GraphNode node3 = new GraphNode(3);
        GraphNode node4 = new GraphNode(4);

        graph.addNode(node1);
        graph.addNode(node2);
        graph.addNode(node3);
        graph.addNode(node4);

        graph.addEdge(node1, node2);
        graph.addEdge(node1, node3);
        graph.addEdge(node2, node4);
        graph.addEdge(node3, node4);

        bfs(node1);
    }
}

代码解释

visited 数组用于记录节点是否被访问过。
Queue 用于存储待访问的节点。
将起始节点加入队列并标记为已访问。
在循环中，从队列中取出节点，访问该节点，并将其未访问的邻居节点加入队列。

常见实践

迷宫问题

在迷宫问题中，我们可以将每个格子看作图的节点，相邻的可通行格子看作邻居节点。通过 BFS 算法，可以找到从起点到终点的最短路径。

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

public class MazeSolver {
    public static int shortestPath(char[][] maze, int[] start, int[] end) {
        int rows = maze.length;
        int cols = maze[0].length;
        boolean[][] visited = new boolean[rows][cols];
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        Queue<int[]> queue = new LinkedList<>();

        queue.add(start);
        visited[start[0]][start[1]] = true;
        int steps = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] current = queue.poll();
                if (current[0] == end[0] && current[1] == end[1]) {
                    return steps;
                }

                for (int[] dir : directions) {
                    int newRow = current[0] + dir[0];
                    int newCol = current[1] + dir[1];

                    while (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && maze[newRow][newCol] == ' ') {
                        newRow += dir[0];
                        newCol += dir[1];
                    }

                    newRow -= dir[0];
                    newCol -= dir[1];

                    if (!visited[newRow][newCol]) {
                        visited[newRow][newCol] = true;
                        queue.add(new int[]{newRow, newCol});
                    }
                }
            }
            steps++;
        }
        return -1;
    }

    public static void main(String[] args) {
        char[][] maze = {
            {' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' '},
            {' ', ' ', ' ', ' '}
        };
        int[] start = {0, 0};
        int[] end = {3, 3};

        int result = shortestPath(maze, start, end);
        System.out.println("Shortest path length: " + result);
    }
}

二叉树层次遍历

在二叉树中，BFS 可以用于层次遍历。以下是一个简单的二叉树层次遍历的实现：

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

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

public class BinaryTreeLevelOrderTraversal {
    public static void levelOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode current = queue.poll();
                System.out.print(current.val + " ");

                if (current.left != null) {
                    queue.add(current.left);
                }
                if (current.right != null) {
                    queue.add(current.right);
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        levelOrderTraversal(root);
    }
}

最佳实践

优化空间复杂度

在某些情况下，如果节点数量非常大，使用布尔数组记录访问状态可能会占用大量内存。可以考虑使用哈希表（HashMap）来代替布尔数组，这样可以节省内存，特别是在节点值范围较大时。

剪枝策略

在搜索过程中，如果发现某些节点明显不可能是最优解的一部分，可以提前剪掉这些分支，从而减少搜索空间，提高算法效率。例如，在迷宫问题中，如果某个方向已经超出了边界或者遇到了障碍物，可以直接跳过该方向的搜索。

双向 BFS

对于一些搜索空间较大的问题，可以使用双向 BFS。双向 BFS 从起始节点和目标节点同时开始搜索，当两个搜索相遇时，就找到了最短路径。这种方法可以显著减少搜索空间，提高算法效率。

小结

BFS 算法是一种强大的搜索算法，在 Java 中有广泛的应用。通过理解其基础概念、掌握在 Java 中的使用方法以及常见实践和最佳实践，开发者可以在解决各种实际问题时，高效地运用 BFS 算法，提高程序的性能和效率。

参考资料

《算法导论》
LeetCode 官方文档
GeeksforGeeks 相关文章