【数据结构】图的广度优先遍历
一.广度优先遍历的基本思想
(1)访问顶点v;
(2)依次访问v的各个未被访问的邻接点v1,v2,v3……,vk;
(3)分别从v1,v2,v3……,vk出发依次访问他们未被访问的邻接点,并使“先被访问顶点的邻接点”先于“后被访问的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。
二.广度优先遍历的伪代码
1.初始化队列Q;
2.访问顶点v;visited[v]=true;顶点v入队列Q;
3.while(队列Q非空)
3.1 v=队列Q的队头元素出队;
3.2 w=顶点v的第一个邻接点;
3.3while(w存在)
3.3.1 如果w未被访问,则访问顶点w;visited[w]=1;顶点w入队;
3.3.2 w=顶点v的下一个邻接点
三.代码实现
template<class T>
void MGraph<T>::BFSTraverse(int v){bool visited[vertexNum]=false;queue<int> Q;int w,i=0,count=0;cout<<vertex[v]<<endl;visited[v]=true;++count;Q.push(v);if(count==vertexNum){return;}while(!Q.empty()){v=Q.front();//队头元素出队Q.pop();for(i=0;i<vertexNum;i++){if(arc[v][i]&&!visited[i]){//w未被访问w=i;cout<<vertex[w]<<endl;visited[w]=true;++count;Q.push(w);}}}}
template <class T>
void ALGraph<T>::BFSTraverse(int v){bool visited[vertexNum]=false;queue<int> Q;int w,i=0,count=0;cout<<adjList[v].vertex<<endl;visited[v]=true;++count;Q.push(v);if(count==vertexNum){return;}while(!Q.empty()){v=Q.front();//队头元素出队Q.pop();struct ArcNode *p=adjList[v].firstEdge;while(p){if(!visited[p->adjvex]){w=p->adjvex;cout<<adjList[w].vertex<<endl;visited[w]=true;++count;Q.push(w);}else{p=p->next;}}}
}
四.总结
广度优先:确定起始节点后,全部邻接点(分支)同时开始遍历;
深度优先:先从一个邻接点(分支)开始遍历,直至该分支全部遍历完成,再遍历按顺序的下一个分支。
相关文章:
【数据结构】图的广度优先遍历
一.广度优先遍历的基本思想 (1)访问顶点v; (2)依次访问v的各个未被访问的邻接点v1,v2,v3……,vk; (3)分别从v1,v2,v3……...
AM@函数展开成幂级数@间接法@常用麦克劳林幂级数展开公式
文章目录 间接法推导幂级数展开常用麦克劳林幂级数展开公式应用例例例 间接法推导幂级数展开 已知函数的幂级数展开公式间接推导其他函数幂级数 使用原始的推导公式推导函数的幂级数展开是繁琐不便的,需要分别计算各项系数 a n f ( n ) ( 0 ) n ! a_{n}\frac{f^{(n)}(0)}{n!}…...
LeetCode994.腐烂的橘子
看完题我觉得这不是和上一道岛屿的题一样简单嘛,然后写了将近2个小时才写出来,我的思路就是,用check()先对grid检查一下,是否有以下情况: (如果有1的周围都是空,则这个位置用不腐烂,…...
【开源】基于Vue和SpringBoot的康复中心管理系统
项目编号: S 056 ,文末获取源码。 \color{red}{项目编号:S056,文末获取源码。} 项目编号:S056,文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 普通用户模块2.2 护工模块2.3 管理员…...
【音视频基础】AVI文件格式
AVI文件采用的是RIFF文件结构方式。波形音频wave,MIDI和数字视频AVI都采用这种格式存储。 AVI文件的整体结构如下图所示 构造RIFF文件的基本单元叫做数据块(Chunk),每个数据块包含3个部分 4字节的数据块标记(或者叫…...
图书馆整理I(从尾到头打印列表),剑指offer,力扣
目录 题目地址: 我们直接看题解吧: 解题方法: 难度分析: 审题目事例提示: 解题思路(辅助栈): 代码(递归): 代码(列表插入): 相似题目对…...
C++编写的多线程自动爬虫程序
目录 引言 一、程序的设计 二、程序的实现 三、程序的测试 四、优化与改进 五、代码示例 总结 引言 随着互联网的快速发展,网络爬虫程序已经成为数据采集、信息处理的重要工具。C作为一种高效的编程语言,具有高效的并发处理能力和丰富的网络编程…...
SMB信息泄露的利用
一、背景 今天分享SMB信息泄露,SMB(Server Message Block)网络通信协议,早些时候被用于Web链接和客户端与服务器之间的信息通信,现在大部分Web页面使用HTTP协议,在web领域应用较少。另一方面SMB协议还是被…...
QT自定义信号,信号emit,信号参数注册
qt如何自定义信号 使用signals声明返回值是void在需要发送信号的地方使用 emit 信号名字(参数)进行发送 在需要链接的地方使用connect进行链接 ct进行链接...
06.webpack性能优化--构建速度
优化babel-loaderhappyPackIgnorePluginparalleUglifyPluginnoParse自动刷新 1 happypack多进程打包 js单线程,开启多进程打包提高构建速度(特别是多核CPU) const HappyPack require(happypack)module.exports smart(webpackCommonConf,…...
11-15 周三 softmax 回归学习
11-15 周三 softmax 回归学习 时间版本修改人描述2023年11月15日11:17:27V0.1宋全恒新建文档 简介 softmax分享可以参考什么是softmax 回归估计一个连续值,分类预测一个离散类别。 恶意软件的判断 回归和分类 分类可以认为从回归的单输出变成多输出 B站学习 softm…...
React新手必懂的知识点
react思想:组件化开发 React 的核心概念是组件化开发,将用户界面拆分成独立的可复用组件。学习如何创建和使用 React 组件,以及组件之间的数据传递和通信是非常重要的。 React的思想就是拆分组件与使用组件。 import React from react;// 定…...
es为什么这么快
es为什么这么快的方式 es的基于Lucene开源搜索引擎,负责文件存储和搜索,支持http请求,以json形式展示 这样介绍你有可能有点迷糊我们详细解释 es 使用的倒排索引的方式,进行数据存储方式,给每一个字段创建索引&…...
Pandas分组聚合_Python数据分析与可视化
Pandas分组聚合 分组单列和多列分组Series 系列分组通过数据类型或者字典分组获取单个分组对分组进行迭代 聚合应用单个聚合函数应用多个聚合函数自定义函数传入 agg() 中对不同的列使用不同的聚合函数 分组聚合的流程主要有三步: 分割步骤将 DataFrame 按照指定的…...
VMware17虚拟机Linux安装教程(详解附图,带VMware Workstation 17 Pro安装)
一、安装 VMware 附官方下载链接(VM 17 pro):https://download3.vmware.com/software/WKST-1701-WIN/VMware-workstation-full-17.0.1-21139696.exe 打开下载好的VMware Workstation 17 Pro安装包; 点击下一步; 勾选我…...
基于SDN技术构建多平面业务承载网络
随着企业数字化的浪潮席卷各个行业,传统网络架构面临着更为复杂和多样化的挑战。企业正在寻找一种全面适应数字化需求的网络解决方案。随着软件定义网络(SDN)的发展,“多业务SDN一张网”解决方案为企业提供了一种全新的网络架构&a…...
关于卓越服务的调研报告
NetSuite知识会发起的本次调研从2023年11月2日开始,到11月12日结束。16日已向参与调研的朋友邮件回复,感谢您的付出!今朝分享此报告,各位同学参考。 调研问题与反馈总结 问题1:您能想到哪些服务组织能够提供高满意度&…...
ubuntu22.04换源
1、系统信息 lsb_release -a No LSB modules are available. Distributor ID: Ubuntu Description: Ubuntu 22.04.3 LTS Release: 22.04 Codename: jammy2、进入 /etc/apt/ 目录: cd /etc/apt/ 3、备份默认源文件 sudo cp sources.list sources.list_bak 4、编…...
03. Python中的语句
1、前言 在《Python基础数据类型》一文中,我们了解了Python中的基础数据类型,今天我们继续了解下Python中的语句和函数。 2、语句 在Python中常用的语句可以大致分为两类:条件语句、循环语句。 2.1、条件语句 条件语句就是我们编码时常见…...
Linux CentOS7 添加网卡
一台主机中安装多块网卡,有许多优势。可以实现多项功能。 为了学习网卡参数的设置,可以为主机添加多块网卡。与添加磁盘一样,要在VMware中设置。利用图形化方式或命令行查看或设置网卡。本文仅初步讨论添加、查看与删除网卡,有关…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存
文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...
iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈
在日常iOS开发过程中,性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期,开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发,但背后往往隐藏着系统资源调度不当…...
【JVM面试篇】高频八股汇总——类加载和类加载器
目录 1. 讲一下类加载过程? 2. Java创建对象的过程? 3. 对象的生命周期? 4. 类加载器有哪些? 5. 双亲委派模型的作用(好处)? 6. 讲一下类的加载和双亲委派原则? 7. 双亲委派模…...
【JVM】Java虚拟机(二)——垃圾回收
目录 一、如何判断对象可以回收 (一)引用计数法 (二)可达性分析算法 二、垃圾回收算法 (一)标记清除 (二)标记整理 (三)复制 (四ÿ…...
TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?
在工业自动化持续演进的今天,通信网络的角色正变得愈发关键。 2025年6月6日,为期三天的华南国际工业博览会在深圳国际会展中心(宝安)圆满落幕。作为国内工业通信领域的技术型企业,光路科技(Fiberroad&…...
保姆级【快数学会Android端“动画“】+ 实现补间动画和逐帧动画!!!
目录 补间动画 1.创建资源文件夹 2.设置文件夹类型 3.创建.xml文件 4.样式设计 5.动画设置 6.动画的实现 内容拓展 7.在原基础上继续添加.xml文件 8.xml代码编写 (1)rotate_anim (2)scale_anim (3)translate_anim 9.MainActivity.java代码汇总 10.效果展示 逐帧…...
