当前位置: 首页 > news >正文

【前端】自学基础算法 -- 21.图的广度优先搜索

图的广度优先搜索

简介

图的广度优先搜索,沿着图的宽度遍历图的节点,先访问离起始节点最近的节点,然后逐渐向外扩展。

基本步骤:

  1. 选择一个起始节点作为当前节点。
  2. 将当前节点加入队列。
  3. 当队列不为空时,重复以下步骤:
    a. 从队列中取出一个节点,作为当前节点。
    b.标记当前节点为已访问。
    c. 对于当前节点的每一个未被访问的相邻节点,将其加入队列。
  4. 重复步骤 3,直到找到目标节点或遍历完整个图。

实现方法

/*** 图的广度优先搜索*/class Node {constructor(value) {this.value = value // 节点的值this.neighbors = [] // 相邻节点的列表}
}// 创建节点
let a = new Node('a')
let b = new Node('b')
let c = new Node('c')
let d = new Node('d')
let e = new Node('e')// 设置节点a的邻居
a.neighbors = [b, c]
// 设置节点b的邻居
b.neighbors = [a, c, d]
// 设置节点c的邻居
c.neighbors = [a, b, d]
// 设置节点d的邻居
d.neighbors = [b, c, e]
// 设置节点e的邻居
e.neighbors = [d]/*** 深度优先搜索* @param {Node} nodes - 当前层节点数组* @param {any} target - 目标值* @param {Node[]} path - 已经访问过的节点路径* @returns {boolean} - 是否找到目标值*/
function bfs(nodes, target, path) {// 如果当前层节点为空,返回falseif (nodes == null || nodes.length == 0) return falselet nextNodes = [] // 存储下一层的节点for (let i = 0; i < nodes.length; i++) {// 如果节点已经访问过,跳过if (path.indexOf(nodes[i]) > -1) continue// 将节点加入已访问路径path.push(nodes[i])// 如果找到目标值,返回trueif (nodes[i].value === target) return true// 将相邻节点加入下一层节点列表else nextNodes = nextNodes.concat(nodes[i].neighbors)}// 递归搜索下一层节点return bfs(nextNodes, target, path)
}// 调用bfs函数,从节点b开始搜索,目标值为'ax'
console.log(bfs([b], 'b', []))

相关文章:

【前端】自学基础算法 -- 21.图的广度优先搜索

图的广度优先搜索 简介 图的广度优先搜索&#xff0c;沿着图的宽度遍历图的节点&#xff0c;先访问离起始节点最近的节点&#xff0c;然后逐渐向外扩展。 基本步骤&#xff1a; 选择一个起始节点作为当前节点。将当前节点加入队列。当队列不为空时&#xff0c;重复以下步骤…...

ChatGPT与Claude AI:两大生成式对话模型的比较分析

自ChatGPT推出以来&#xff0c;这款强大的AI聊天机器人迅速吸引了全球的关注。其出色的对话能力和多样化的应用场景&#xff0c;成为许多人初次体验基于大规模语言模型的潜力。然而&#xff0c;在这个快速发展的领域中&#xff0c;另一款AI也在悄然崭露头角&#xff0c;那就是由…...

前端开发:盒子模型、块元素

1.border边框 *{box-sizing:border-box; } //使所有边框不再撑大盒子模型 粗细 : border-width 样式 : border-style, 默认没边框 . solid 实线边框 dashed 虚线边框 dotted 点线边框 颜色 : border-color div { width : 200px ; height : 200px ; border : …...

升级 CentOS 7.x 系统内核到 4.4 版本

问题描述 在 CentOS 7.x 系统中&#xff0c;默认内核版本是 3.10.x&#xff0c;这个版本可能会带来一些与 Docker 和 Kubernetes 兼容性的问题&#xff0c;导致系统性能不稳定或功能异常。为了提高系统的稳定性和兼容性&#xff0c;建议升级到更高版本的内核&#xff0c;例如 …...

播放音频文件同步音频文本

播放音频同步音频文本 对应单个文本高亮显示 使用audio音频文件对应音频文本资源 音频文本内容&#xff08;Json&#xff09; [{"end": 4875,"index": 0,"speaker": 0,"start": 30,"text": "70号二啊,","tex…...

springboot使用Easy Excel导出列表数据为Excel

springboot使用Easy Excel导出列表数据为Excel Easy Excel官网&#xff1a;https://easyexcel.opensource.alibaba.com/docs/current/quickstart/write 主要记录一下引入时候的pom&#xff0c;直接引入会依赖冲突 解决方法&#xff1a; <!-- 引入Easy Excel的依赖 -->&l…...

day07_Spark SQL

文章目录 day07_Spark SQL课程笔记一、今日课程内容二、Spark SQL函数定义&#xff08;掌握&#xff09;1、窗口函数2、自定义函数背景2.1 回顾函数分类标准:SQL最开始是_内置函数&自定义函数_两种 2.2 自定义函数背景 3、Spark原生自定义UDF函数3.1 自定义函数流程&#x…...

高性能现代PHP全栈框架 Spiral

概述 Spiral Framework 诞生于现实世界的软件开发项目是一个现代 PHP 框架&#xff0c;旨在为更快、更清洁、更卓越的软件开发提供动力。 特性 高性能 由于其设计以及复杂精密的应用服务器&#xff0c;Spiral Framework框架在不影响代码质量以及与常用库的兼容性的情况下&a…...

LeetCode - #182 Swift 实现找出重复的电子邮件

网罗开发 &#xff08;小红书、快手、视频号同名&#xff09; 大家好&#xff0c;我是 展菲&#xff0c;目前在上市企业从事人工智能项目研发管理工作&#xff0c;平时热衷于分享各种编程领域的软硬技能知识以及前沿技术&#xff0c;包括iOS、前端、Harmony OS、Java、Python等…...

《解锁鸿蒙Next系统人工智能语音助手开发的关键步骤》

在当今数字化时代&#xff0c;鸿蒙Next系统与人工智能的融合为开发者带来了前所未有的机遇&#xff0c;开发一款人工智能语音助手应用更是备受关注。以下是在鸿蒙Next系统上开发人工智能语音助手应用的关键步骤&#xff1a; 环境搭建与权限申请 安装开发工具&#xff1a;首先需…...

【Linux网络编程】数据链路层 | MAC帧 | ARP协议

前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站 &#x1f308;个人主页&#xff1a; 南桥几晴秋 &#x1f308;C专栏&#xff1a; 南桥谈C &#x1f308;C语言专栏&#xff1a; C语言学习系…...

《自动驾驶与机器人中的SLAM技术》ch7:基于 ESKF 的松耦合 LIO 系统

目录 基于 ESKF 的松耦合 LIO 系统 1 坐标系说明 2 松耦合 LIO 系统的运动和观测方程 3 松耦合 LIO 系统的数据准备 3.1 CloudConvert 类 3.2 MessageSync 类 4 松耦合 LIO 系统的主要流程 4.1 IMU 静止初始化 4.2 ESKF 之 运动过程——使用 IMU 预测 4.3 使用 IMU 预测位姿进…...

基于spingbott+html+Thymeleaf的24小时智能服务器监控平台设计与实现

博主介绍&#xff1a;硕士研究生&#xff0c;专注于信息化技术领域开发与管理&#xff0c;会使用java、标准c/c等开发语言&#xff0c;以及毕业项目实战✌ 从事基于java BS架构、CS架构、c/c 编程工作近16年&#xff0c;拥有近12年的管理工作经验&#xff0c;拥有较丰富的技术架…...

全栈面试(一)Basic/微服务

文章目录 项目地址一、Basic InterviewQuestions1. tell me about yourself?2. tell me about a time when you had to solve a complex code problem?3. tell me a situation that you persuade someone at work?4. tell me a about a confict with a teammate and how you…...

python安装完成后可以进行的后续步骤和注意事项

安装Python3完成后&#xff0c;你可以开始使用它进行编程和开发。以下是一些安装完成后可以进行的后续步骤和注意事项&#xff1a; 验证安装 检查Python版本&#xff1a; 打开“终端”应用程序。输入python3 --version&#xff0c;应该显示安装的Python3版本号。 检查pip版本…...

[Qt] 窗口 | 菜单栏MenuBar

目录 QMainWindow 概述 一、菜单栏 1、创建菜单栏 2、在菜单栏中添加菜单 3、创建菜单项 4、在菜单项之间添加分割线 5、添加快捷键 6、添加子菜单 7、添加图标 综合示例 QMainWindow 概述 Qt 窗口是通过 QMainWindow 类来实现的。 QMainWindow 是一个为用户 提供主…...

[读书日志]从零开始学习Chisel 第十三篇:Scala的隐式参数与隐式转换(敏捷硬件开发语言Chisel与数字系统设计)

10. 隐式转换与隐式参数 假设编写了一个向量类MyVector&#xff0c;并且包含一些向量的基本操作。因为向量可以与标量做数乘运算&#xff0c;所以需要一个计算数乘的方法“*”&#xff0c;它应该接收一个类型为基本值类的参数&#xff0c;在向量对象myVec调用该方法时&#xf…...

CMake学习笔记(1)

1. CMake概述 CMake 是一个项目构建工具&#xff0c;并且是跨平台的。关于项目构建我们所熟知的还有Makefile&#xff08;通过 make 命令进行项目的构建&#xff09;&#xff0c;大多是IDE软件都集成了make&#xff0c;比如&#xff1a;VS 的 nmake、linux 下的 GNU make、Qt …...

cursor+deepseek构建自己的AI编程助手

文章目录 准备工作在Cursor中添加deepseek 准备工作 下载安装Cursor &#xff08;默认安装在C盘&#xff09; 注册deepseek获取API key 在Cursor中添加deepseek 1、打开cursor&#xff0c;选择设置 选择Model&#xff0c;添加deepseek-chat 注意这里去掉其他的勾选项&…...

Kotlin实现DataBinding结合ViewModel的时候,提示找不到Unresolved reference: BR解决方案

在用Kotlin语言实现DataBinding结合ViewModel的代码的时候&#xff0c;如下所示&#xff1a; class UserModel(private val userName: String, private val userAge: Int) : BaseObservable() {get:Bindablevar name: String userNameset (value) {field valuenotifyPropert…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...