BFS 和 DFS(深度优先搜索、广度优先搜索)
深度优先搜索(DFS)和广度优先搜索(BFS)是两种常用的图遍历算法,用于解决图相关的问题。它们在搜索问题中具有广泛的应用,如路径搜索、连通性检测等。
以下是具体区别:

(图片引自:https://www.cnblogs.com/xuxinstyle/p/13261651.html)
深度优先搜索(DFS)
深度优先搜索是一种先探索到尽可能深的节点,再回溯到之前的节点的搜索策略。在实现上,DFS通常使用递归或栈来实现。
模板:
def dfs(node, visited):if node in visited:returnvisited.add(node)# Process current node# Explore neighborsfor neighbor in node.neighbors:dfs(neighbor, visited)
讲解:
1. 从起始节点开始,访问当前节点并标记为已访问。
2. 对当前节点的邻居节点进行遍历,若邻居节点未被访问过,则以该邻居节点为新的当前节点,继续进行深度优先搜索。
3. 递归地进行上述步骤,直到所有可达节点都被访问。
例题:
问题:给定一个无向图,判断是否存在从节点A到节点B的路径。
def hasPath(graph, start, end):"""判断是否存在从start到end的路径Args:graph: 图的邻接表表示start: 起始节点end: 目标节点Returns:bool: 如果存在路径返回True,否则返回False"""visited = set()return dfs(start, end, visited, graph)def dfs(node, end, visited, graph):"""深度优先搜索的辅助函数Args:node: 当前节点end: 目标节点visited: 已访问过的节点集合graph: 图的邻接表表示Returns:bool: 如果存在路径返回True,否则返回False"""if node == end:return Truevisited.add(node)for neighbor in graph[node]:if neighbor not in visited:if dfs(neighbor, end, visited, graph):return Truereturn False
广度优先搜索(BFS)
广度优先搜索是一种先探索到当前节点的所有邻居节点,再逐层向外搜索的策略。通常使用队列来实现。把每个还没有搜索到的点依次放入队列,然后再弹出队列的头部元素当做当前遍历点。模板:
from collections import dequedef bfs(start):"""广度优先搜索Args:start: 起始节点Returns:None"""queue = deque([start])visited = set()while queue:node = queue.popleft()if node not in visited:visited.add(node)# Process current node# 处理当前节点# Explore neighbors# 探索当前节点的邻居节点for neighbor in node.neighbors:queue.append(neighbor)
要点
1. 将起始节点加入队列,并标记为已访问。
2. 当队列不为空时,弹出队首节点,对其未被访问的邻居节点进行遍历。
3. 将未被访问的邻居节点加入队列,并标记为已访问。
4. 重复上述步骤,直到队列为空。
分类模板:如果不需要确定当前遍历到了哪一层,模板如下(这里参考:https://www.cnblogs.com/xuxinstyle/p/13261651.html)
while queue 不空:cur = queue.pop()for 节点 in cur的所有相邻节点:if 该节点有效且未访问过:queue.push(该节点)
如果要确定当前遍历到了哪一层,BFS模板如下
这里增加了level表示当前遍历到二叉树中的哪一层了,也可以理解为在一个图中,现在已经走了多少步了。size表示在当前遍历层有多少个元素,也就是队列中的元素数,我们把这些元素一次性遍历完,即把当前层的所有元素都向外走了一步。
level = 0
while queue 不空:size = queue.size()while (size --) {cur = queue.pop()for 节点 in cur的所有相邻节点:if 该节点有效且未被访问过:queue.push(该节点)}level ++;
例题:
问题:给定一个无向图,从节点A开始,找到到节点B的最短路径的长度。
from collections import dequedef shortestPath(graph, start, end):"""寻找从start到end的最短路径长度Args:graph: 图的邻接表表示start: 起始节点end: 目标节点Returns:int: 最短路径长度,如果不存在路径则返回-1"""queue = deque([(start, 0)])visited = set()while queue:node, distance = queue.popleft()if node == end:return distancevisited.add(node)for neighbor in graph[node]:if neighbor not in visited:queue.append((neighbor, distance + 1))return -1 # If no path found# Example graph representation: {node: [neighbors]}
graph = {'A': ['B', 'C'],'B': ['A', 'D', 'E'],'C': ['A', 'F'],'D': ['B'],'E': ['B', 'F'],'F': ['C', 'E']
}print(shortestPath(graph, 'A', 'F')) # Output: 2
这里使用了BFS算法来搜索从节点A到节点B的最短路径的长度。
下面是代码的一些区别:这里使用字典来存图
BFS实现
#BFS实现
graph = {"A":["B","C"],"B":["A","C","D"],"C":["A","B","D","F"],"D":["B","C","E","F"],"E":["C","D"],"F":["D"]}
def BFS(graph,s):queue = []queue.append(s)#将元素 s 加入到队列的尾部(队尾)seen = set()#储存出现过的量seen.add(s)while(len(queue)>0):vertex = queue.pop(0)#从队列的头部(队首)弹出元素nodes = graph[vertex]#vertex的所有临接点for w in nodes:if w not in seen:queue.append(w)seen.add(w)print(vertex)
BFS(graph,"A")
DFS实现 队列—>栈
graph = {"A":["B","C"],"B":["A","C","D"],"C":["A","B","D","F"],"D":["B","C","E","F"],"E":["C","D"],"F":["D"]}
def BFS(graph,s):queue = []queue.append(s)seen = set()#储存出现过的量seen.add(s)while(len(queue)>0):vertex = queue.pop()#pop(0)->pop() 先弹出最后一个元素 这里体现出栈nodes = graph[vertex]#vertex的所有临接点for w in nodes:if w not in seen:queue.append(w)seen.add(w)print(vertex)BFS(graph,"A")
相关文章:
BFS 和 DFS(深度优先搜索、广度优先搜索)
深度优先搜索(DFS)和广度优先搜索(BFS)是两种常用的图遍历算法,用于解决图相关的问题。它们在搜索问题中具有广泛的应用,如路径搜索、连通性检测等。 以下是具体区别: (图片引自&am…...
Casbin 权限管理介绍及在 Go 语言中的使用入门
引言 在现代软件开发过程中,权限管理是一个至关重要的环节,它关系到系统的安全性和用户体验。Casbin 是一个强大的访问控制库,支持多种访问控制模型,如 ACL(访问控制列表)、RBAC(基于角色的访问…...
Two Sum
声明:博主为算法新手,博客仅作为个人学习记录 作为新手我的做法 (1)数组nums遍历一遍挑选出小于target的值及其下标,值存入temp,下标存到indices (2)遍历temp找到符合temp[i]temp[j]target的两个…...
3.3.2 交易体系构建——缠论操作思路
本节我们基于交易目标(规避下跌趋势,参与上涨趋势)来构建基于上涨趋势的缠论交易体系。建立上涨趋势的缠论交易体系需要以下几个步骤: 识别下跌走势大概率完成的位置 等待出现转折结构 确定交易模型并交易 从概率的角度来说,判断走势结束是个概率事件。为构建成功较高的交…...
[SQL] 事务的四大特性(ACID)
🎄事务的四大特性 以下就是事务的四大特性,简称ACID。 原子性📢事务时不可分割的最小操作单元,要么全部成功,要么全部失败。一致性📢事务完成后,必须使所有的数据都保持一致隔离性📢…...
使用 Three.js 实现流光特效
大家好!我是 [数擎AI],一位热爱探索新技术的前端开发者,在这里分享前端和 Web3D、AI 技术的干货与实战经验。如果你对技术有热情,欢迎关注我的文章,我们一起成长、进步! 开发领域:前端开发 | AI…...
Error [ERR_REQUIRE_ESM]: require() of ES Module
报错信息: 【报错】Message.js 导入方式不对,用的是 ES Moudle 的语法,提示使用 import 引入文件 项目开发没有用到 js-message 依赖,是 node-ipc 依赖中用到的 js-message 依赖, node-ipc 中限制 js-message 版本&a…...
沉浸式翻译插件深度评测:打破语言壁垒的黑科技利器
在信息爆炸的时代,语言障碍成为了许多人获取信息的一大难题。尤其是在浏览外文网站、观看外语视频或阅读外文文档时,语言不通往往会让人倍感困扰。然而,一款名为沉浸式翻译的黑科技插件,却以其强大的翻译能力和便捷的使用体验,成为了众多用户打破语言壁垒的首选工具。本文…...
Java 中 HTTP 协议版本使用情况剖析
Java 中 HTTP 协议版本使用情况剖析 一、HTTP/1.1 与 HTTP/2 概述 (一)HTTP/1.1 HTTP/1.1 是广泛应用且成熟的 HTTP 协议版本,它在互联网发展历程中扮演了重要角色。其特点主要包括: 连接方式:默认采用短连接,即每次请求都要建立新的 TCP 连接,请求完成后断开。不过也…...
蓝桥杯学习大纲
(致酷德与热爱算法、编程的小伙伴们) 在查阅了相当多的资料后,发现没有那篇博客、文章很符合我们备战蓝桥杯的学习路径。所以,干脆自己整理一篇,欢迎大家补充! 一、题型分布: 题型分布为填空…...
VSCode ssh远程连接内网服务器(不能上网的内网环境的Linux服务器)的终极解决方案
VSCode ssh远程连接内网服务器(不能上网的内网环境的Linux服务器) 离线下载vscode-server并安装: 如果远程端不能联网可以下载包离线安装,下载 vscode-server 的 url 需要和 vscode 客户端版本的 commit-id 对应.通过 vscode 面板的帮助->关于可以获…...
【多模态处理篇五】【DeepSeek文档解析:PDF/Word智能处理引擎】
你知道吗?全球每天产生的PDF文档超过10亿份,但90%的上班族还在用复制粘贴的笨办法处理文档!DeepSeek文档解析引擎就像给你的电脑装上了"文档翻译官",能把PDF/Word里的文字、表格、公式甚至排版样式都变成AI能理解的"语言"。举个真实场景:法务小姐姐用…...
STM32-心知天气项目
一、项目需求 使用 ESP8266 通过 HTTP 获取天气数据(心知天气),并显示在 OLED 屏幕上。 按键 1 :循环切换今天 / 明天 / 后天天气数据; 按键 2 :更新天气。 二、项目框图 三、cjson作用 https://gi…...
cs106x-lecture14(Autumn 2017)-SPL实现
打卡cs106x(Autumn 2017)-lecture14 (以下皆使用SPL实现,非STL库,后续课程结束会使用STL实现) 1、min Write a function named min that accepts a pointer to a ListNode representing the front of a linked list. Your function should return the …...
基于STM32的智能家居语音系统(单片机毕设)
前言 源代码下载链接: https://download.csdn.net/download/m0_74712453/90071680 需要实物的可以私信博主或者在文章最下方添加好友。 目录 一、项目介绍和演示视频 二、硬件实现 1. 材料材料 2. 原理图和PCB 三、软件实现 1. 代码解析 1.1 main函数 1.2…...
ASP.NET Core 简单文件上传
使用异步 JavaScript 和 XML(AJAX)进行简单的文件上传;用 C# 编写的服务器端代码。 使用AJAX和ASP.NET Core MVC上传文件再简单不过了。这不依赖于jQuery。此代码允许上传多个文件,并与 .NET Core 3.1、.NET 6和.NET 8兼容。 如果…...
2502C++,C++继承的多态性
构 A{单 向量<串>记;元<类 T>静 空 ff(串&a){清理(记);名向量(a,记);串 b{"---ff---"};打印(b);T::g();} };构 B:公 A{元<类 T>静 空 f(){串 a{"错误.txt"};ff<T>(a);} };构 C:公 A{元<类 T>静 空 f(){串 a{"a12.c…...
【机器学习】13.十大算法之一K均值算法(K-means)聚类详细讲解
【机器学习】13.十大算法之一K均值算法(K-means)聚类详细讲解 一摘要二个人简介三K-均值聚类(K-means)3.1-K均值算法的基本原理3.1.1- 聚类分析的目标3.1.2- K - means算法算法原理 四K-means聚类算法的收敛性五证明K均值算法的收…...
Spring扩展点之Mybatis整合模拟
Spring扩展点之Mybatis整合 单独使用MyBaitis模拟整合MyBatis到Spring 单独使用MyBaitis 通过配置文件生成sqlSessionFactory,用sqlSessionFactory开启session。通过session获取到mapper执行对应的sql。 InputStream inputStream Resources.getResourceAsStream(…...
.NET MVC实现电影票管理
.NET MVC(Model-View-Controller)是微软推出的基于 Model-View-Controller 设计模式的 Web 应用框架,属于 ASP.NET Core 的重要组成部分。其核心目标是通过清晰的分层架构实现 高内聚、低耦合 的开发模式,适用于构建可扩展的企业级…...
抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...
使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...
搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...
【Linux系统】Linux环境变量:系统配置的隐形指挥官
。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量:setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...
毫米波雷达基础理论(3D+4D)
3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文: 一文入门汽车毫米波雷达基本原理 :https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...
Python 训练营打卡 Day 47
注意力热力图可视化 在day 46代码的基础上,对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...
