建设银行信用卡管理中心网站app下载微信
什么是广度优先搜索 (BFS)?
想象一下你在玩一个迷宫游戏，你需要找到从起点到终点的最短路径。广度优先搜索 (BFS) 就像是你在迷宫中逐层探索的过程：
- 先探索距离起点最近的所有位置
- 然后探索距离起点第二近的所有位置
- 以此类推，直到找到终点
BFS 的核心思想是 "逐层扩展"，它使用队列来实现这种扩展方式。
BFS 算法的基本步骤
-
准备工作：
- 创建一个队列，将起点放入队列
- 创建一个访问标记，标记起点已被访问
-
循环扩展：
- 当队列不为空时，取出队列头部元素
- 检查该元素是否是目标
- 如果不是，将该元素的所有未访问邻居加入队列
- 标记这些邻居为已访问
-
结束条件：
- 找到目标元素，返回结果
- 队列为空，说明无法到达目标
BFS vs DFS
BFS 和深度优先搜索 (DFS) 是两种基本的图遍历算法，它们的区别可以用一个形象的比喻来说明：
- BFS：像是地毯式搜索，逐层推进，适合找最短路径
- DFS：像是一条路走到黑，适合找所有可能的路径
102.二叉树的层序遍历
题目描述
给你一个二叉树，请你返回其按层序遍历得到的节点值。 （即逐层地，从左到右访问所有节点）。
解题思路
这道题是 BFS 的典型应用。我们需要：
- 从根节点开始，逐层遍历二叉树
- 每一层的节点值放在一个列表中
- 最终返回这些列表的集合
想象一下，我们有一个队列，就像一个传送带：
- 首先把根节点放在传送带上
- 然后每次从传送带上取出一个节点
- 把这个节点的左右子节点（如果有）放在传送带的末尾
- 重复这个过程，直到传送带上没有节点
这样就能保证我们按照层次顺序遍历二叉树。
例题代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();List<List<Integer>> res = new ArrayList<>();if (root != null) queue.add(root);while (!queue.isEmpty()) {List<Integer> tmp = new ArrayList<>();for(int i = queue.size(); i > 0; i--) {TreeNode node = queue.poll();tmp.add(node.val);if (node.left != null) queue.add(node.left);if (node.right != null) queue.add(node.right);}res.add(tmp);}return res;}
}执行速度
希望本文能够帮助读者更深入地理解广度优先搜索(BFS)，并在实际项目中发挥其优势。谢谢阅读！
希望这份博客能够帮助到你。如果有其他需要修改或添加的地方，请随时告诉我。
