深入理解广度优先搜索（BFS）

为什么学习BFS？

BFS是解决最短路径问题（在无权图中）、连通性检测、层级遍历等任务的基础。掌握图的遍历算法对学习更高级的数据结构和算法至关重要。

Java实现BFS的步骤

1. 创建图的数据结构（通常用邻接表）
2. 初始化一个队列，用于存储待访问的节点
3. 使用布尔数组记录已访问的节点，防止重复访问
4. 从起始节点开始，将其加入队列并标记为已访问
5. 循环处理队列中的节点，直到队列为空

完整Java代码示例

下面是一个使用邻接表表示图，并实现BFS算法实现的完整Java程序：

import java.util.*;public class BFSExample {    // 使用邻接表表示图    private List<List<Integer>> graph;    private int vertices;    public BFSExample(int vertices) {        this.vertices = vertices;        graph = new ArrayList<>(vertices);        for (int i = 0; i < vertices; i++) {            graph.add(new ArrayList<>());        }    }    // 添加边    public void addEdge(int u, int v) {        graph.get(u).add(v);        graph.get(v).add(u); // 无向图    }    // 广度优先搜索    public void bfs(int startVertex) {        boolean[] visited = new boolean[vertices];        Queue<Integer> queue = new LinkedList<>();        visited[startVertex] = true;        queue.offer(startVertex);        System.out.print("BFS遍历顺序: ");        while (!queue.isEmpty()) {            int current = queue.poll();            System.out.print(current + " ");            // 遍历当前节点的所有邻居            for (int neighbor : graph.get(current)) {                if (!visited[neighbor]) {                    visited[neighbor] = true;                    queue.offer(neighbor);                }            }        }        System.out.println();    }    public static void main(String[] args) {        BFSExample bfs = new BFSExample(6);        bfs.addEdge(0, 1);        bfs.addEdge(0, 2);        bfs.addEdge(1, 3);        bfs.addEdge(1, 4);        bfs.addEdge(2, 5);        bfs.bfs(0); // 从节点0开始BFS    }}

代码解析

- graph 是一个列表的列表，每个索引代表一个顶点，其值是该顶点连接的所有邻居。

- bfs 方法使用 LinkedList 作为队列，确保先进先出的访问顺序。

- visited 数组防止重复访问同一个节点，这是避免无限循环的关键。

时间与空间复杂度

- 时间复杂度：O(V + E)，其中 V 是顶点数，E 是边数。每个顶点和每条边最多被访问一次。

- 空间复杂度：O(V)，用于存储队列和 visited 数组。

应用场景

• 社交网络中查找两人之间的最短关系链
• 迷宫求解（寻找最短路径）
• 网页爬虫按层级抓取页面
• 垃圾回收中的对象可达性分析

总结

通过本教程，你已经掌握了Java广度优先搜索的基本原理、实现方法和应用场景。BFS是Java数据结构教程中不可或缺的一部分，建议多动手练习，加深理解。

继续探索深度优先搜索（DFS），你会发现两种遍历方式各有优势，适用于不同场景！