温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

Java广度优先遍历怎么实现

发布时间:2021-12-08 14:06:44 来源:亿速云 阅读:248 作者:iii 栏目:大数据
# 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(); // 换行表示新层级 } } 

3.2 图的BFS实现(邻接表表示)

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

3.3 二维矩阵的BFS(迷宫问题)

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的变种与应用进阶

4.1 双向BFS优化

当知道起点和终点时,可以从两端同时进行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; // 未找到路径 } 

4.2 多源BFS

适用于有多个起点的场景,如”腐烂的橘子”问题。

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

五、BFS常见问题与解决方案

5.1 内存消耗过大

问题:当图规模很大时,队列可能消耗过多内存 解决方案: 1. 使用双向BFS减少搜索空间 2. 采用迭代加深搜索(IDS)限制深度 3. 使用磁盘存储部分队列数据

5.2 重复访问问题

问题:节点可能被重复加入队列 解决方案: 1. 在入队时立即标记为已访问 2. 使用更高效的数据结构如BitSet进行标记

5.3 最短路径记录

需求:需要记录到达每个节点的最短路径 实现方法

// 在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的比较

特性 BFS DFS
数据结构 队列
空间复杂度 O(V)在最坏情况下 O(d)其中d是最大深度
最短路径 天然支持 需要额外处理
实现方式 迭代 递归/迭代
适用场景 最短路径、连通性 拓扑排序、环路检测

七、性能优化技巧

  1. 队列选择:根据场景选择合适队列实现

    • LinkedList:通用选择
    • ArrayDeque:更优性能(Java推荐)
    • PriorityQueue:带优先级的情况
  2. 访问标记优化

    // 使用BitSet替代HashSet BitSet visited = new BitSet(); visited.set(node.id); 
  3. 并行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. 单词接龙等)进行实践练习。 “`

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI