广度优先遍历(BFS):逐层探索的智慧
引言:什么是广度优先遍历?
广度优先遍历(BFS)是一种用于遍历或搜索树(Tree)和图(Graph)结构的算法。其核心思想是逐层访问节点,先访问离起点最近的节点,再逐步向外扩展。BFS 被广泛应用于最短路径查找、社交网络分析、迷宫求解等领域。本文将通过实例详细解析 BFS 的工作原理、实现方式及其实际应用。
一、BFS 的算法原理
1.1 核心思想:队列与分层遍历
BFS 的关键在于使用**队列(Queue)**这一数据结构。算法步骤如下:
-
将起点加入队列,并标记为已访问。
-
循环执行以下操作,直到队列为空:
-
从队列中取出一个节点(队首元素)。
-
访问该节点的所有未被访问的邻居节点,依次加入队列并标记为已访问。
-
通过这种方式,BFS 保证了所有节点按距离起点的层级顺序被访问。
1.2 算法伪代码
def BFS(graph, start):queue = deque([start]) # 初始化队列visited = set([start]) # 记录已访问节点while queue:node = queue.popleft() # 取出队首节点print(node) # 处理节点(例如打印)for neighbor in graph[node]: # 遍历邻居if neighbor not in visited:visited.add(neighbor)queue.append(neighbor)
二、实例解析:BFS 如何工作?
2.1 实例1:二叉树的层次遍历
问题描述:给定一棵二叉树,按层输出所有节点的值(从左到右)。
输入二叉树:
复制
1/ \2 3/ \ /4 5 6
BFS 过程:
-
初始队列:
[1],访问第1层:1。 -
处理节点1,将其子节点2、3入队。队列:
[2, 3],访问第2层:2, 3。 -
处理节点2,子节点4、5入队。队列:
[3, 4, 5]。 -
处理节点3,子节点6入队。队列:
[4, 5, 6],访问第3层:4, 5, 6。 -
处理剩余节点(均为叶子节点),队列逐步清空。
输出结果:[[1], [2,3], [4,5,6]]。
代码实现(Python):
from collections import dequeclass TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef level_order(root):if not root:return []queue = deque([root])result = []while queue:level_size = len(queue)current_level = []for _ in range(level_size):node = queue.popleft()current_level.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)result.append(current_level)return result# 测试代码
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
print(level_order(root)) # 输出:[[1], [2, 3], [4, 5, 6]]
2.2 实例2:图的社交网络好友推荐
问题描述:在社交网络中,如何找到某个用户的“二度好友”(好友的好友),并按距离排序?
输入图结构(邻接表表示):
graph = { 'Alice': ['Bob', 'Charlie'], 'Bob': ['Alice', 'Diana', 'Eve'], 'Charlie': ['Alice', 'Frank'], 'Diana': ['Bob'], 'Eve': ['Bob', 'Grace'], 'Frank': ['Charlie'], 'Grace': ['Eve'] }
BFS 过程(以 Alice 为起点):
-
第0层(直接好友):
Bob, Charlie。 -
第1层(二度好友):
Diana, Eve, Frank(通过 Bob 和 Charlie 访问)。 -
第2层(三度好友):
Grace(通过 Eve 访问)。
输出结果:
-
二度好友:
Diana, Eve, Frank(距离为2)。
代码实现:
from collections import dequedef find_second_degree_friends(graph, start):queue = deque([(start, 0)]) # (节点, 距离)visited = {start: 0}second_degree = []while queue:user, distance = queue.popleft()if distance == 2:second_degree.append(user)for neighbor in graph[user]:if neighbor not in visited:visited[neighbor] = distance + 1queue.append((neighbor, distance + 1))return second_degree# 测试
print(find_second_degree_friends(graph, 'Alice')) # 输出:['Diana', 'Eve', 'Frank']
2.3 实例3:迷宫最短路径
问题描述:在一个二维矩阵表示的迷宫中(0代表可通行,1代表障碍),求从起点到终点的最短路径。
输入迷宫:
[[0, 1, 0, 0],[0, 0, 0, 1],[0, 1, 0, 0],[0, 0, 0, 0] ] 起点 (0,0),终点 (3,3)。
BFS 过程:
-
从起点 (0,0) 开始,向四个方向(上下左右)探索。
-
逐层记录可达的坐标,并标记已访问。
-
第一次到达终点 (3,3) 时的路径即为最短路径。
最短路径长度:6步(路径示例:(0,0) → (1,0) → (1,1) → (1,2) → (2,2) → (3,2) → (3,3))。
代码实现:
from collections import dequedef shortest_path(maze, start, end):rows = len(maze)cols = len(maze[0])directions = [(-1,0), (1,0), (0,-1), (0,1)] # 上下左右queue = deque([(start[0], start[1], 0)]) # (x, y, 步数)visited = set([(start[0], start[1])])while queue:x, y, steps = queue.popleft()if (x, y) == end:return stepsfor dx, dy in directions:nx, ny = x + dx, y + dyif 0 <= nx < rows and 0 <= ny < cols:if maze[nx][ny] == 0 and (nx, ny) not in visited:visited.add((nx, ny))queue.append((nx, ny, steps + 1))return -1 # 不可达
# 测试 maze = [[0, 1, 0, 0],[0, 0, 0, 1],[0, 1, 0, 0],[0, 0, 0, 0] ] print(shortest_path(maze, (0,0), (3,3))) # 输出:6
三、BFS 的应用场景
3.1 最短路径问题
-
无权图的最短路径:BFS 天然保证首次访问到目标节点的路径是最短的(如迷宫问题)。
-
网络路由算法:路由器使用类似 BFS 的算法寻找最短跳数路径。
3.2 社交网络分析
-
好友推荐:查找用户的二度、三度好友。
-
影响力传播模型:模拟信息在社交网络中的扩散过程。
3.3 状态空间搜索
-
八数码问题:通过 BFS 找到从初始状态到目标状态的最少移动次数。
-
游戏 AI(如象棋、围棋):生成所有可能的走法并评估最优解。
四、BFS 与 DFS 的对比
| 特性 | BFS | DFS |
|---|---|---|
| 数据结构 | 队列(Queue) | 栈(Stack) |
| 空间复杂度 | 高(存储所有当前层节点) | 低(存储路径上的节点) |
| 适用场景 | 最短路径、分层遍历 | 拓扑排序、连通性检测、回溯问题 |
| 解的性质 | 首次找到的解一定最优 | 可能找到非最优解 |
五、总结
广度优先遍历通过逐层扫描的方式,为解决最短路径、层级关系分析等问题提供了高效的方法。其核心在于队列的先进先出(FIFO)特性,确保节点按距离顺序被处理。无论是社交网络中的好友推荐,还是迷宫中的最短路径查找,BFS 都展现了其强大的实用性。理解 BFS 不仅有助于掌握算法基础,更能培养“分层思考”的编程思维。
相关文章:
广度优先遍历(BFS):逐层探索的智慧
引言:什么是广度优先遍历? 广度优先遍历(BFS)是一种用于遍历或搜索树(Tree)和图(Graph)结构的算法。其核心思想是逐层访问节点,先访问离起点最近的节点,再逐…...
网络HTTP
HTTP Network Request Library A Retrofit-based HTTP network request encapsulation library that provides simple and easy-to-use API interfaces with complete network request functionality. 基于Retrofit的HTTP网络请求封装库,提供简单易用的API接口和完…...
(七)企业级高性能 WEB 服务 - HTTPS 加密
在当今互联网时代,数据安全成为了每个企业和开发者必须关注的重点。尤其是对于Web服务来说,如何保障用户数据的安全传输是至关重要的。本文将深入探讨HTTPS加密的原理、Nginx的HTTPS配置,以及如何通过Nginx实现高性能的Web服务。 1. HTTPS加密…...
[HTTP协议]应用层协议HTTP从入门到深刻理解并落地部署自己的云服务(2)
标题:[HTTP协议]应用层协议HTTP从入门到深刻理解并落地部署自己的云服务(2) 水墨不写bug 文章目录 一、无法拷贝类(class uncopyable)的设计解释:重要思想:使用示例 二、锁的RAII设计解释重要考虑使用示例 三、基于RAII模式和互斥锁的的日志…...
MySQL(单表)知识点
文章目录 1.数据库的概念2.下载并配置MySQL2.1初始化MySQL的数据2.2注册MYSQL服务2.3启动MYSQL服务2.4修改账户默认密码2.5登录MYSQL2.6卸载MYSQL 3.MYSQL数据模型3.1连接数据库 4.SQL简介4.1SQL的通用语法4.2SQL语句的分类4.3DDL语句4.3.1数据库4.3.2表(创建,查询,修改,删除)4…...
HarmonyOS Next 属性动画和转场动画
HarmonyOS Next 属性动画和转场动画 在鸿蒙应用开发中,动画是提升用户体验的关键要素。通过巧妙运用动画,我们能让应用界面更加生动、交互更加流畅,从而吸引用户的注意力并增强其使用粘性。鸿蒙系统为开发者提供了丰富且强大的动画开发能力&…...
使用Node.js从零搭建DeepSeek本地部署(Express框架、Ollama)
目录 1.安装Node.js和npm2.初始化项目3.安装Ollama4.下载DeepSeek模型5.创建Node.js服务器6.运行服务器7.Web UI对话-Chrome插件-Page Assist 1.安装Node.js和npm 首先确保我们机器上已经安装了Node.js和npm。如果未安装,可以通过以下链接下载并安装适合我们操作系…...
Docker 部署 MongoDB 并持久化数据
Docker 部署 MongoDB 并持久化数据 在现代开发中,MongoDB 作为 NoSQL 数据库广泛应用,而 Docker 则提供了高效的容器化方案。本教程将介绍如何使用 Docker 快速部署 MongoDB,并实现数据持久化,确保数据不会因容器重启或删除而丢失…...
DeepSeek + 沉浸式翻译 打造智能翻译助手
本文详细介绍如何使用 DeepSeek API 沉浸式翻译插件打造个性化翻译助手。 一、DeepSeek API 配置 基础配置 API 基础地址:https://api.deepseek.com需要申请 API Key支持与 OpenAI SDK 兼容的调用方式 可用模型 deepseek-chat:已升级为 DeepSeek-V3&am…...
cdn取消接口缓存
添加cdn后,使用cdn加速域名访问接口 是缓存,不是最新的数据,如果使用局域网则是最新的数据,如果修改配置,确保使用cdn域名请求的接口返回不是缓存 要确保通过CDN加速域名访问接口时返回的是最新的数据,而不…...
字节跳动C++客户端开发实习生内推-抖音基础技术
智能手机爱好者和使用者,追求良好的用户体验; 具有良好的编程习惯,代码结构清晰,命名规范; 熟练掌握数据结构与算法、计算机网络、操作系统、编译原理等课程; 熟练掌握C/C/OC/Swift一种或多种语言ÿ…...
OpenHarmony子系统开发编译构建指导
OpenHarmony子系统开发编译构建指导 概述 OpenHarmony编译子系统是以GN和Ninja构建为基座,对构建和配置粒度进行部件化抽象、对内建模块进行功能增强、对业务模块进行功能扩展的系统,该系统提供以下基本功能: 以部件为最小粒度拼装产品和独…...
MySQL进阶-关联查询优化
采用左外连接 下面开始 EXPLAIN 分析 EXPLAIN SELECT SQL_NO_CACHE * FROM type LEFT JOIN book ON type.card book.card; 结论:type 有All ,代表着全表扫描,效率较差 添加索引优化 ALTER TABLE book ADD INDEX Y ( card); #【被驱动表】࿰…...
数据结构第六节:二叉搜索树(BST)的基本操作与实现
【本节要点】 二叉搜索树(BST)基本原理代码实现核心操作实现辅助函数测试代码完整代码 一、二叉搜索树(BST)基本原理与设计总结 注:基本原理的详细分析可以在数据结构第六节中查看,这里是简单描述。 二叉搜…...
在昇腾GPU上部署DeepSeek大模型与OpenWebUI:从零到生产的完整指南
引言 随着国产AI芯片的快速发展,昇腾(Ascend)系列GPU凭借其高性能和兼容性,逐渐成为大模型部署的重要选择。本文将以昇腾300i为例,手把手教你如何部署DeepSeek大模型,并搭配OpenWebUI构建交互式界面。无论…...
在window终端创建docker容器的问题
问题: 错误原因: PowerShell 换行符错误 PowerShell 中换行应使用反引号而非反斜杠 \,错误的换行符导致命令解析中断。 在 Windows 的 PowerShell 中运行 Docker 命令时遇到「sudo 无法识别」的问题,这是因为 Windows 系统原生不…...
掌握Kubernetes Network Policy,构建安全的容器网络
在 Kubernetes 集群中,默认情况下,所有 Pod 之间都是可以相互通信的,这在某些场景下可能会带来安全隐患。为了实现更精细的网络访问控制,Kubernetes 提供了 Network Policy 机制。Network Policy 允许我们定义一组规则,…...
ReAct论文阅读笔记总结
ReAct:Synergizing Reasoning and Acting in Language Models 背景 最近的研究结果暗示了在自主系统中结合语言推理与交互决策的可能性。 一方面,经过适当Prompt的大型语言模型(LLMs)已经展示了在算术、常识和符号推理任务中通…...
Linux云计算SRE-第十七周
1. 做三个节点的redis集群。 1、编辑redis节点node0(10.0.0.100)、node1(10.0.0.110)、node2(10.0.0.120)的安装脚本 [rootnode0 ~]# vim install_redis.sh#!/bin/bash # 指定脚本解释器为bashREDIS_VERSIONredis-7.2.7 # 定义Redis的版本号PASSWORD123456 # 设置Redis的访问…...
Python在数字货币交易中的算法设计:从策略到实践
Python在数字货币交易中的算法设计:从策略到实践 随着区块链技术的发展和加密货币市场的繁荣,数字货币交易已经成为金融领域的一个重要分支。从个体投资者到量化基金,算法交易(Algorithmic Trading)正在为提高交易效率和决策质量提供强大的支撑。在这些技术应用中,Pytho…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
CMake基础:构建流程详解
目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...
jmeter聚合报告中参数详解
sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample(样本数) 表示测试中发送的请求数量,即测试执行了多少次请求。 单位,以个或者次数表示。 示例:…...
【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?
FTP(File Transfer Protocol)本身是一个基于 TCP 的协议,理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况,主要原因包括: ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...
【Ftrace 专栏】Ftrace 参考博文
ftrace、perf、bcc、bpftrace、ply、simple_perf的使用Ftrace 基本用法Linux 利用 ftrace 分析内核调用如何利用ftrace精确跟踪特定进程调度信息使用 ftrace 进行追踪延迟Linux-培训笔记-ftracehttps://www.kernel.org/doc/html/v4.18/trace/events.htmlhttps://blog.csdn.net/…...
Python爬虫(四):PyQuery 框架
PyQuery 框架详解与对比 BeautifulSoup 第一部分:PyQuery 框架介绍 1. PyQuery 是什么? PyQuery 是一个 Python 的 HTML/XML 解析库,它采用了 jQuery 的语法风格,让开发者能够用类似前端 jQuery 的方式处理文档解析。它的核心特…...
