BFS 队列实现 详解

BFS 队列实现详解

BFS（广度优先搜索，Breadth-First Search）是一种经典的图搜索算法，广泛应用于图论问题、树的遍历、最短路径寻找等场景。BFS 的核心思想是利用队列来实现逐层搜索。

BFS 的基本思想

特点：按照层次（或距离）依次遍历图或树的节点。队列的作用：存储当前层的节点，并在访问当前层节点后将下一层的节点加入队列。访问顺序：

先访问起始节点，再访问与其直接相连的所有节点（即第一层节点），然后再访问这些节点的相邻节点（第二层节点），依此类推。

适用场景：

图的最短路径问题（无权图）。判断连通性问题。树的层序遍历。

BFS 的核心实现步骤

队列初始化：

将起始节点加入队列。通常用 Queue（如 LinkedList）来实现。

标记访问：

使用一个 visited 数组（或集合）记录已访问的节点，避免重复访问。

队列循环：

从队列中取出一个节点，进行访问。将该节点的所有未访问过的邻居节点加入队列。

结束条件：

队列为空，表示所有能访问的节点都已被访问。

BFS 模板代码（伪代码）

BFS(graph, startNode):

初始化队列 queue

初始化 visited 集合或数组

将起始节点 startNode 加入队列

将 startNode 标记为已访问

while queue 非空:

从队列中取出当前节点 current

访问当前节点（处理逻辑）

for 邻居节点 neighbor in current 的所有邻居:

if neighbor 未被访问:

将 neighbor 加入队列

将 neighbor 标记为已访问

Java 实现示例

1. 无权图的最短路径

import java.util.*;

public class BFSExample {

public static void main(String[] args) {

// 图的邻接表表示法

Map> graph = new HashMap<>();

graph.put(1, Arrays.asList(2, 3));

graph.put(2, Arrays.asList(4, 5));

graph.put(3, Arrays.asList(6));

graph.put(4, Arrays.asList());

graph.put(5, Arrays.asList());

graph.put(6, Arrays.asList());

// 调用 BFS 方法

bfs(graph, 1);

}

public static void bfs(Map> graph, int startNode) {

Queue queue = new LinkedList<>(); // 队列存储节点

Set visited = new HashSet<>(); // 集合记录已访问节点

queue.add(startNode); // 起始节点入队

visited.add(startNode); // 标记起始节点为已访问

while (!queue.isEmpty()) {

int current = queue.poll(); // 取出队首元素

System.out.println("Visited: " + current);

// 遍历当前节点的邻居节点

for (int neighbor : graph.getOrDefault(current, new ArrayList<>())) {

if (!visited.contains(neighbor)) {

queue.add(neighbor); // 邻居节点入队

visited.add(neighbor); // 标记为已访问

}

}

}

}

}

输出：

Visited: 1

Visited: 2

Visited: 3

Visited: 4

Visited: 5

Visited: 6

2. 最短路径问题（无权图）

import java.util.*;

public class ShortestPathBFS {

public static void main(String[] args) {

// 图的邻接表表示法

Map> graph = new HashMap<>();

graph.put(1, Arrays.asList(2, 3));

graph.put(2, Arrays.asList(4, 5));

graph.put(3, Arrays.asList(6));

graph.put(4, Arrays.asList());

graph.put(5, Arrays.asList());

graph.put(6, Arrays.asList());

// 调用最短路径方法

int shortestPath = shortestPathBFS(graph, 1, 6);

System.out.println("Shortest Path: " + shortestPath);

}

public static int shortestPathBFS(Map> graph, int start, int target) {

Queue queue = new LinkedList<>();

Map distances = new HashMap<>(); // 记录起始点到每个节点的距离

queue.add(start);

distances.put(start, 0); // 起始点的距离为 0

while (!queue.isEmpty()) {

int current = queue.poll();

// 如果到达目标节点，返回距离

if (current == target) {

return distances.get(current);

}

for (int neighbor : graph.getOrDefault(current, new ArrayList<>())) {

if (!distances.containsKey(neighbor)) { // 邻居未访问

queue.add(neighbor);

distances.put(neighbor, distances.get(current) + 1); // 更新距离

}

}

}

return -1; // 如果无法到达目标节点，返回 -1

}

}

输出：

Shortest Path: 2

3. 二叉树的层序遍历

import java.util.*;

class TreeNode {

int val;

TreeNode left, right;

TreeNode(int val) {

this.val = val;

}

}

public class BFSBinaryTree {

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

root.right.left = new TreeNode(6);

// 层序遍历

List> result = levelOrderTraversal(root);

System.out.println(result);

}

public static List> levelOrderTraversal(TreeNode root) {

List> result = new ArrayList<>();

if (root == null) return result;

Queue queue = new LinkedList<>();

queue.add(root);

while (!queue.isEmpty()) {

int levelSize = queue.size(); // 当前层的节点数量

List level = new ArrayList<>();

for (int i = 0; i < levelSize; i++) {

TreeNode current = queue.poll();

level.add(current.val);

if (current.left != null) queue.add(current.left);

if (current.right != null) queue.add(current.right);

}

result.add(level);

}

return result;

}

}

输出：

[[1], [2, 3], [4, 5, 6]]

BFS 的复杂度分析

时间复杂度：

遍历每个节点一次，访问每条边一次。时间复杂度为 O(V+E)O(V + E)O(V+E)，其中 VVV 是节点数，EEE 是边数。

空间复杂度：

主要由队列和 visited 记录占用空间。空间复杂度为 O(V)O(V)O(V)。

常见问题与解决

重复访问节点：

解决：使用 visited 集合或数组来记录访问状态。

多目标搜索：

解决：将多个起点同时加入队列，记录各自的层次。

稠密图的性能问题：

解决：优化邻接表存储，减少无效边的遍历。

总结

BFS 是一种经典的搜索算法，队列是其核心数据结构，用于按层次管理节点访问顺序。通过 Queue 的先进先出（FIFO）特性，可以确保节点按距离或层次依次访问，实现简单且高效。