# 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进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。