数据结构--BFS求最短路
数据结构–BFS求最短路
BFS求⽆权图的单源最短路径
注:⽆权图可以视为⼀种特殊的带权图,只是每条边的权值都为1
以 2 为 b e g i n 位置 以2为begin位置 以2为begin位置
代码实现
//求顶点u到其他顶点的最短路径
void BFS_MIN_Distance(Graph G, int u)
{//d[i]表示从u到i结点的最短路径for(i = 0; i < G.vexnum; ++i){d[i] = inf; //初始化路径长度path[i] = -1; //最短路径从哪个顶点过来}d[u] = 0;visited[u] = TRUE;EnQueue(Q, u);while(!isEmpty(Q))//BFS算法主过程{DeQueue(Q, u); //队头元素u出队for(w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w)){if(!visited[w])//w为u的尚未访问的邻接顶点{d[w] = d[u] + 1; //路径长度加1path[w] = u; //最短路径应从u到Wvisited[w] = TRUE; //设已访问标记EnQueue(Q, w); //顶点w入队}}}
}
上图最终 d[]、 path[]、 visited[] 的情况
将其生成⼴度优先⽣成树
就是对BFS的⼩修改,在visit⼀个顶点时,修改
其最短路径⻓度 d[ ] 并在 path[ ] 记录前驱结点
2到8的最短路径⻓度 = d[8] = 3
通过path数组可知,2到8的最短路径为: 2 → 6 → 7 → 8 2\to6\to7\to8 2→6→7→8
相关文章:
数据结构--BFS求最短路
数据结构–BFS求最短路 BFS求⽆权图的单源最短路径 注:⽆权图可以视为⼀种特殊的带权图,只是每条边的权值都为1 以 2 为 b e g i n 位置 以2为begin位置 以2为begin位置 代码实现 //求顶点u到其他顶点的最短路径 void BFS_MIN_Distance(Graph G, int u…...
FPGA应用学习笔记----定点除法的gold算法流水线设计
猜一个Y0 a和b上下都Y0 分母越接近一,分子就越接近答案 误差: 下一步迭代为 Y的迭代值: 误差值: 代码的实现如上所示...
Nginx转发的原理和负载均衡
一、Nginx转发的原理 Nginx是一个高性能的反向代理服务器,它可以用于实现请求的转发和负载均衡。以下是Nginx转发的基本原理: 客户端发送请求:客户端向Nginx服务器发送HTTP请求。 Nginx接收请求:Nginx服务器接收到客户端的请求。…...
怎么换ip地址 电脑切换ip地址方法
互联网时代,IP地址是我们在网络上进行通信和访问的身份标识。有时候,我们可能需要更改IP地址,以便获得更好的网络体验或绕过某些限制。本文将介绍如何使用深度IP转换器来更改IP地址。 1:了解IP地址 IP地址是一个由数字和点组成的标…...
软件设计基础
巩固基础,砥砺前行 。 只有不断重复,才能做到超越自己。 能坚持把简单的事情做到极致,也是不容易的。 软件项目管理。 在经历了软件危机和大连的软件项目失败以后,人们对软件工程专业的现状进行了多次分析。得出了普遍性的结论&…...
OptaPlanner笔记5
2.4 与spring boot集成 2.4.4 添加依赖 <dependency><groupId>org.optaplanner</groupId><artifactId>optaplanner-spring-boot-starter</artifactId> </dependency>2.4.8 创建求解器服务 import org.optaplanner.core.api.solver.Solv…...
PS注意事项优漫动游
PS入门注意事项AdobePhotoshop是目前最流行的平面设计软件之一。可以说,只要你接触平面设计,那么无论早晚,你都要和它打交道。关于Photoshop,要说的实在太多太多,但不论你想让它成为你的左膀右臂,或者仅仅是…...
matplotlib 判断鼠标是否点击在当前线上
在开发中有一个需求:对生成的一条线进行拖拽。 我将这个方法实现在线所在的类里,这个过程中需要判断鼠标是否点击在当前线上,从而实现拖拽。 实现代码如下: # 点击事件 def on_press(self,event):if event.inaxes ! self.ax:retur…...
bash中(冒号破折号)的用法 —— 筑梦之路
${PUBLIC_INTERFACE:-eth0} :- 的用途是什么? 含义:如果 $PUBLIC_INTERFACE 存在且不是 null,则返回其值,否则返回 "eth0"。 ${parameter:-word} 使用默认值。如果 parameter 未设置或为 null,则 word 的扩…...
LeetCode150道面试经典题--同构字符串(简单)
1.题目 给定两个字符串 s 和 t ,判断它们是否是同构的。如果 s 中的字符可以按某种映射关系替换得到 t ,那么这两个字符串是同构的。每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序。不同字符不能映射到同一个字符上,…...
Redis - 数据类型映射底层结构
简介 从数据类型上体现就是,同一个数据类型,在不同的情况下会使用不同的编码类型,底层所使用的的数据结构也不相同。 字符串对象 字符串对象的编码可以是 int、raw 和 embstr 三者之一。 embstr 编码是专门用于保存简短字符串的一种优化编…...
MySQL数据库表的增删查改 - 进阶
一,数据库约束 1.1 约束对象 not null - 该列不能为空unique - 保证该列的每一行都不一样default - 规定没有给列赋值时的默认值(自定义)primary key - not null 和 unique 的结合,会给该列添加一个索引࿰…...
8086汇编语言工作环境 百度网盘下载
链接:https://pan.baidu.com/s/1-1K7gX859xejaUK70OTgtw?pwdbfa5 提取码:bfa5 为了方便下载,找了很多资料,也是从其他人那边分享过来的,也方便其他人 文件内容:...
ES6 解构
解构的语法 … {} 解构的语法中,...(展开运算符)和 {}(对象字面量)扮演着不同的角色。 ...(展开运算符): 在解构中,... 被用作展开运算符,用于将数组或对象中…...
React三个状态时触发的相应钩子
01.初始化状态。 这个阶段由render()函数触发; 1.constructor(); 2.componentWillMount(); 在17版本以后改为UNSAFE_componentWillMount() reason:react为组件异步渲染做准备; 3.render(); 4.componentDidMount(); 这…...
阿里云服务器部署Drupal网站教程基于CentOS系统
阿里云百科分享如何在CentOS 7操作系统的ECS实例上搭建Drupal电子商务网站。Drupal是使用PHP语言编写的开源内容管理框架(CMF),它由内容管理系统(CMS)和PHP开发框架(Framework)共同构成。它用于…...
【广州华锐视点】VR燃气轮机故障判断模拟演练系统
VR燃气轮机故障判断模拟演练系统由广州华锐视点开发,是一款基于虚拟现实技术的教育工具,旨在为学生提供一个安全、高效、互动的学习环境,帮助他们更好地掌握燃气轮机的故障诊断技能。 这款VR实训软件能够模拟真实的燃气轮机故障诊断场景&…...
第01天 什么是CSRF ?
✅作者简介:大家好,我是Leo,热爱Java后端开发者,一个想要与大家共同进步的男人😉😉 🍎个人主页:Leo的博客 💞当前专栏: 每天一个知识点 ✨特色专栏࿱…...
uniapp 自定义手机顶部状态栏不生效问题
想要的效果想淘宝一样,底色覆盖到手机顶部,找了两天都没找到原因,过程很艰苦,直接上结果吧 项目是后来接手的,最终原因出在这, "immersed" : false>设置为 true 就可以了,沉浸式样…...
C++语法中bitset位图介绍及模拟实现
一、位图的引入 先来看下边一道面试题: 给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。 经过我们之前的学习,我们可能会有以下的思路: 对这些数进行排序ÿ…...
业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
站群服务器的应用场景都有哪些?
站群服务器主要是为了多个网站的托管和管理所设计的,可以通过集中管理和高效资源的分配,来支持多个独立的网站同时运行,让每一个网站都可以分配到独立的IP地址,避免出现IP关联的风险,用户还可以通过控制面板进行管理功…...
STM32HAL库USART源代码解析及应用
STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...
2.3 物理层设备
在这个视频中,我们要学习工作在物理层的两种网络设备,分别是中继器和集线器。首先来看中继器。在计算机网络中两个节点之间,需要通过物理传输媒体或者说物理传输介质进行连接。像同轴电缆、双绞线就是典型的传输介质,假设A节点要给…...
codeforces C. Cool Partition
目录 题目简述: 思路: 总代码: https://codeforces.com/contest/2117/problem/C 题目简述: 给定一个整数数组,现要求你对数组进行分割,但需满足条件:前一个子数组中的值必须在后一个子数组中…...
数据库管理与高可用-MySQL故障排查与生产环境优化
目录 #1.1MySQL单案例故障排查 1.1.1MySQL常见的故障排查 1.1.2MySQL主从故障排查 #2.1MySQL优化 2.1.1硬件方面的优化 2.1.2进程方面的优化 #3.1MySQL存储引擎 3.1.1 MyISAM存储引擎 3.1.2 InnoDB存储引擎 1.1MySQL单案例故障排查 1.1.1MySQL常见的故障排查 (1&…...
python3GUI--基于PyQt5+DeepSort+YOLOv8智能人员入侵检测系统(详细图文介绍)
文章目录 一.前言二.技术介绍1.PyQt52.DeepSort3.卡尔曼滤波4.YOLOv85.SQLite36.多线程7.入侵人员检测8.ROI区域 三.核心功能1.登录注册1.登录2.注册 2.主界面1.主界面简介2.数据输入3.参数配置4.告警配置5.操作控制台6.核心内容显示区域7.检…...
