广度优先遍历(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…...
UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...
聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
