数据结构--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亿个数中。 经过我们之前的学习,我们可能会有以下的思路: 对这些数进行排序ÿ…...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...
srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...
排序算法总结(C++)
目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指:同样大小的样本 **(同样大小的数据)**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...
Matlab实现任意伪彩色图像可视化显示
Matlab实现任意伪彩色图像可视化显示 1、灰度原始图像2、RGB彩色原始图像 在科研研究中,如何展示好看的实验结果图像非常重要!!! 1、灰度原始图像 灰度图像每个像素点只有一个数值,代表该点的亮度(或…...
ThreadLocal 源码
ThreadLocal 源码 此类提供线程局部变量。这些变量不同于它们的普通对应物,因为每个访问一个线程局部变量的线程(通过其 get 或 set 方法)都有自己独立初始化的变量副本。ThreadLocal 实例通常是类中的私有静态字段,这些类希望将…...
游戏开发中常见的战斗数值英文缩写对照表
游戏开发中常见的战斗数值英文缩写对照表 基础属性(Basic Attributes) 缩写英文全称中文释义常见使用场景HPHit Points / Health Points生命值角色生存状态MPMana Points / Magic Points魔法值技能释放资源SPStamina Points体力值动作消耗资源APAction…...
