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

数据结构--BFS求最短路

数据结构–BFS求最短路

BFS求⽆权图的单源最短路径

注:⽆权图可以视为⼀种特殊的带权图,只是每条边的权值都为1

以 2 为 b e g i n 位置 以2为begin位置 2begin位置

代码实现

//求顶点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 2678

相关文章:

数据结构--BFS求最短路

数据结构–BFS求最短路 BFS求⽆权图的单源最短路径 注&#xff1a;⽆权图可以视为⼀种特殊的带权图&#xff0c;只是每条边的权值都为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 分母越接近一&#xff0c;分子就越接近答案 误差&#xff1a; 下一步迭代为 Y的迭代值&#xff1a; 误差值&#xff1a; 代码的实现如上所示...

Nginx转发的原理和负载均衡

一、Nginx转发的原理 Nginx是一个高性能的反向代理服务器&#xff0c;它可以用于实现请求的转发和负载均衡。以下是Nginx转发的基本原理&#xff1a; 客户端发送请求&#xff1a;客户端向Nginx服务器发送HTTP请求。 Nginx接收请求&#xff1a;Nginx服务器接收到客户端的请求。…...

怎么换ip地址 电脑切换ip地址方法

互联网时代&#xff0c;IP地址是我们在网络上进行通信和访问的身份标识。有时候&#xff0c;我们可能需要更改IP地址&#xff0c;以便获得更好的网络体验或绕过某些限制。本文将介绍如何使用深度IP转换器来更改IP地址。 1&#xff1a;了解IP地址 IP地址是一个由数字和点组成的标…...

软件设计基础

巩固基础&#xff0c;砥砺前行 。 只有不断重复&#xff0c;才能做到超越自己。 能坚持把简单的事情做到极致&#xff0c;也是不容易的。 软件项目管理。 在经历了软件危机和大连的软件项目失败以后&#xff0c;人们对软件工程专业的现状进行了多次分析。得出了普遍性的结论&…...

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是目前最流行的平面设计软件之一。可以说&#xff0c;只要你接触平面设计&#xff0c;那么无论早晚&#xff0c;你都要和它打交道。关于Photoshop&#xff0c;要说的实在太多太多&#xff0c;但不论你想让它成为你的左膀右臂&#xff0c;或者仅仅是…...

matplotlib 判断鼠标是否点击在当前线上

在开发中有一个需求&#xff1a;对生成的一条线进行拖拽。 我将这个方法实现在线所在的类里&#xff0c;这个过程中需要判断鼠标是否点击在当前线上&#xff0c;从而实现拖拽。 实现代码如下&#xff1a; # 点击事件 def on_press(self,event):if event.inaxes ! self.ax:retur…...

bash中(冒号破折号)的用法 —— 筑梦之路

${PUBLIC_INTERFACE:-eth0} :- 的用途是什么&#xff1f; 含义&#xff1a;如果 $PUBLIC_INTERFACE 存在且不是 null&#xff0c;则返回其值&#xff0c;否则返回 "eth0"。 ${parameter:-word} 使用默认值。如果 parameter 未设置或为 null&#xff0c;则 word 的扩…...

LeetCode150道面试经典题--同构字符串(简单)

1.题目 给定两个字符串 s 和 t &#xff0c;判断它们是否是同构的。如果 s 中的字符可以按某种映射关系替换得到 t &#xff0c;那么这两个字符串是同构的。每个出现的字符都应当映射到另一个字符&#xff0c;同时不改变字符的顺序。不同字符不能映射到同一个字符上&#xff0c…...

Redis - 数据类型映射底层结构

简介 从数据类型上体现就是&#xff0c;同一个数据类型&#xff0c;在不同的情况下会使用不同的编码类型&#xff0c;底层所使用的的数据结构也不相同。 字符串对象 字符串对象的编码可以是 int、raw 和 embstr 三者之一。 embstr 编码是专门用于保存简短字符串的一种优化编…...

MySQL数据库表的增删查改 - 进阶

一&#xff0c;数据库约束 1.1 约束对象 not null - 该列不能为空unique - 保证该列的每一行都不一样default - 规定没有给列赋值时的默认值&#xff08;自定义&#xff09;primary key - not null 和 unique 的结合&#xff0c;会给该列添加一个索引&#xff0…...

8086汇编语言工作环境 百度网盘下载

链接&#xff1a;https://pan.baidu.com/s/1-1K7gX859xejaUK70OTgtw?pwdbfa5 提取码&#xff1a;bfa5 为了方便下载&#xff0c;找了很多资料&#xff0c;也是从其他人那边分享过来的&#xff0c;也方便其他人 文件内容&#xff1a;...

ES6 解构

解构的语法 … {} 解构的语法中&#xff0c;...&#xff08;展开运算符&#xff09;和 {}&#xff08;对象字面量&#xff09;扮演着不同的角色。 ...&#xff08;展开运算符&#xff09;&#xff1a; 在解构中&#xff0c;... 被用作展开运算符&#xff0c;用于将数组或对象中…...

React三个状态时触发的相应钩子

01.初始化状态。 这个阶段由render&#xff08;&#xff09;函数触发&#xff1b; 1.constructor(); 2.componentWillMount(); 在17版本以后改为UNSAFE_componentWillMount() reason&#xff1a;react为组件异步渲染做准备&#xff1b; 3.render(); 4.componentDidMount(); 这…...

阿里云服务器部署Drupal网站教程基于CentOS系统

阿里云百科分享如何在CentOS 7操作系统的ECS实例上搭建Drupal电子商务网站。Drupal是使用PHP语言编写的开源内容管理框架&#xff08;CMF&#xff09;&#xff0c;它由内容管理系统&#xff08;CMS&#xff09;和PHP开发框架&#xff08;Framework&#xff09;共同构成。它用于…...

【广州华锐视点】VR燃气轮机故障判断模拟演练系统

VR燃气轮机故障判断模拟演练系统由广州华锐视点开发&#xff0c;是一款基于虚拟现实技术的教育工具&#xff0c;旨在为学生提供一个安全、高效、互动的学习环境&#xff0c;帮助他们更好地掌握燃气轮机的故障诊断技能。 这款VR实训软件能够模拟真实的燃气轮机故障诊断场景&…...

第01天 什么是CSRF ?

✅作者简介&#xff1a;大家好&#xff0c;我是Leo&#xff0c;热爱Java后端开发者&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f34e;个人主页&#xff1a;Leo的博客 &#x1f49e;当前专栏&#xff1a; 每天一个知识点 ✨特色专栏&#xff1…...

uniapp 自定义手机顶部状态栏不生效问题

想要的效果想淘宝一样&#xff0c;底色覆盖到手机顶部&#xff0c;找了两天都没找到原因&#xff0c;过程很艰苦&#xff0c;直接上结果吧 项目是后来接手的&#xff0c;最终原因出在这&#xff0c; "immersed" : false>设置为 true 就可以了&#xff0c;沉浸式样…...

C++语法中bitset位图介绍及模拟实现

一、位图的引入 先来看下边一道面试题&#xff1a; 给40亿个不重复的无符号整数&#xff0c;没排过序。给一个无符号整数&#xff0c;如何快速判断一个数是否在这40亿个数中。 经过我们之前的学习&#xff0c;我们可能会有以下的思路&#xff1a; 对这些数进行排序&#xff…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

vulnyx Blogger writeup

信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面&#xff0c;gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress&#xff0c;说明目标所使用的cms是wordpress&#xff0c;访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...