您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# Java广度优先遍历怎么实现
## 一、广度优先遍历概述
广度优先遍历（Breadth-First Search，简称BFS）是一种经典的图遍历算法，它以"层级递进"的方式访问图中的所有节点。该算法从起始节点开始，先访问所有相邻节点，然后再依次访问这些相邻节点的相邻节点，以此类推。
### 1.1 基本特点
- **队列结构**：使用队列（FIFO）保存待访问节点
- **层级遍历**：保证先访问完第n层的所有节点，再访问n+1层节点
- **最短路径**：在无权图中可找到两点间最短路径
- **时间复杂度**：O(V+E)，V为顶点数，E为边数
### 1.2 应用场景
- 社交网络中的好友推荐
- 网络爬虫的页面抓取
- 迷宫最短路径求解
- 计算机网络中的广播路由
## 二、BFS算法实现原理
### 2.1 核心步骤
1. 将起始节点放入队列并标记为已访问
2. 从队列头部取出一个节点
3. 访问该节点的所有未访问邻接节点，放入队列尾部并标记
4. 重复步骤2-3直到队列为空
### 2.2 伪代码表示
BFS(起始节点 start): 创建队列queue 创建访问标记集合visited
queue.enqueue(start)
visited.add(start)
while queue不为空:
current = queue.dequeue()
处理current节点
for neighbor in current的所有邻接节点:
if neighbor未访问:
queue.enqueue(neighbor)
visited.add(neighbor)
## 三、Java实现BFS的三种典型场景
### 3.1 二叉树的BFS实现
```java
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public void bfsTree(TreeNode root) {
if (root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
System.out.print(node.val + " ");
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
System.out.println(); // 换行表示新层级
}
}
import java.util.*;
class Graph {
private int V; // 顶点数
private LinkedList<Integer> adj[]; // 邻接表
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
void addEdge(int v, int w) {
adj[v].add(w);
}
void BFS(int s) {
boolean visited[] = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
visited[s] = true;
queue.add(s);
while (!queue.isEmpty()) {
s = queue.poll();
System.out.print(s + " ");
Iterator<Integer> i = adj[s].listIterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n]) {
visited[n] = true;
queue.add(n);
}
}
}
}
}
public class MazeSolver {
// 方向数组：上、右、下、左
private static final int[][] DIRECTIONS = {{-1,0}, {0,1}, {1,0}, {0,-1}};
public static void bfsMaze(int[][] maze, int[] start) {
int rows = maze.length;
int cols = maze[0].length;
boolean[][] visited = new boolean[rows][cols];
Queue<int[]> queue = new LinkedList<>();
queue.offer(start);
visited[start[0]][start[1]] = true;
while (!queue.isEmpty()) {
int[] current = queue.poll();
System.out.println("访问位置: (" + current[0] + "," + current[1] + ")");
// 探索四个方向
for (int[] dir : DIRECTIONS) {
int newRow = current[0] + dir[0];
int newCol = current[1] + dir[1];
if (newRow >= 0 && newRow < rows &&
newCol >= 0 && newCol < cols &&
maze[newRow][newCol] == 0 && // 0表示可通行
!visited[newRow][newCol]) {
visited[newRow][newCol] = true;
queue.offer(new int[]{newRow, newCol});
}
}
}
}
}
当知道起点和终点时，可以从两端同时进行BFS，显著减少搜索空间。
public int bidirectionalBFS(Node start, Node end) {
Set<Node> visited = new HashSet<>();
Set<Node> startSet = new HashSet<>();
Set<Node> endSet = new HashSet<>();
startSet.add(start);
endSet.add(end);
int level = 0;
while (!startSet.isEmpty() && !endSet.isEmpty()) {
// 总是从较小集合开始扩展
if (startSet.size() > endSet.size()) {
Set<Node> temp = startSet;
startSet = endSet;
endSet = temp;
}
Set<Node> nextLevel = new HashSet<>();
for (Node node : startSet) {
if (endSet.contains(node)) {
return level;
}
visited.add(node);
for (Node neighbor : node.neighbors) {
if (!visited.contains(neighbor)) {
nextLevel.add(neighbor);
}
}
}
startSet = nextLevel;
level++;
}
return -1; // 未找到路径
}
适用于有多个起点的场景，如”腐烂的橘子”问题。
public int orangesRotting(int[][] grid) {
Queue<int[]> queue = new LinkedList<>();
int fresh = 0;
int minutes = 0;
// 初始化所有腐烂橘子位置
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 2) {
queue.offer(new int[]{i, j});
} else if (grid[i][j] == 1) {
fresh++;
}
}
}
// 标准BFS过程
while (!queue.isEmpty() && fresh > 0) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] point = queue.poll();
for (int[] dir : DIRECTIONS) {
int x = point[0] + dir[0];
int y = point[1] + dir[1];
if (x >= 0 && y >= 0 &&
x < grid.length && y < grid[0].length &&
grid[x][y] == 1) {
grid[x][y] = 2;
queue.offer(new int[]{x, y});
fresh--;
}
}
}
minutes++;
}
return fresh == 0 ? minutes : -1;
}
问题：当图规模很大时，队列可能消耗过多内存 解决方案： 1. 使用双向BFS减少搜索空间 2. 采用迭代加深搜索（IDS）限制深度 3. 使用磁盘存储部分队列数据
问题：节点可能被重复加入队列 解决方案： 1. 在入队时立即标记为已访问 2. 使用更高效的数据结构如BitSet进行标记
需求：需要记录到达每个节点的最短路径 实现方法：
// 在BFS中增加parent映射
Map<Node, Node> parent = new HashMap<>();
parent.put(start, null);
// 在遍历邻居时记录
if (!visited.contains(neighbor)) {
parent.put(neighbor, current);
// ...其余逻辑
}
// 回溯路径
List<Node> path = new ArrayList<>();
for (Node at = end; at != null; at = parent.get(at)) {
path.add(at);
}
Collections.reverse(path);
| 特性 | BFS | DFS |
|---|---|---|
| 数据结构 | 队列 | 栈 |
| 空间复杂度 | O(V)在最坏情况下 | O(d)其中d是最大深度 |
| 最短路径 | 天然支持 | 需要额外处理 |
| 实现方式 | 迭代 | 递归/迭代 |
| 适用场景 | 最短路径、连通性 | 拓扑排序、环路检测 |
队列选择：根据场景选择合适队列实现
访问标记优化：
// 使用BitSet替代HashSet
BitSet visited = new BitSet();
visited.set(node.id);
并行BFS：对于大规模图，可考虑并行化处理
queue.parallelStream().forEach(node -> {
// 处理节点
});
public List<User> recommendFriends(User user, int depth) {
Set<User> visited = new HashSet<>();
Queue<User> queue = new LinkedList<>();
Map<User, Integer> distances = new HashMap<>();
PriorityQueue<User> recommendations = new PriorityQueue<>(
(a,b) -> distances.get(a) - distances.get(b));
queue.offer(user);
visited.add(user);
distances.put(user, 0);
while (!queue.isEmpty()) {
User current = queue.poll();
if (distances.get(current) >= depth) break;
for (User friend : current.getFriends()) {
if (!visited.contains(friend)) {
visited.add(friend);
distances.put(friend, distances.get(current) + 1);
queue.offer(friend);
// 推荐非直接好友
if (distances.get(friend) > 1) {
recommendations.add(friend);
}
}
}
}
return new ArrayList<>(recommendations);
}
BFS作为基础算法，其Java实现需要注意： 1. 正确处理队列的入队出队顺序 2. 及时标记已访问节点避免重复 3. 根据具体场景选择合适的变种算法 4. 注意处理边界条件和异常情况
掌握BFS不仅能解决许多算法问题，更能培养层级化思考问题的能力。建议读者通过LeetCode等平台上的相关题目（如102. 二叉树的层序遍历、127. 单词接龙等）进行实践练习。 “`
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。