【数据结构】图的广度优先遍历
一.广度优先遍历的基本思想
(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中设置。利用图形化方式或命令行查看或设置网卡。本文仅初步讨论添加、查看与删除网卡,有关…...
MedGemma X-Ray技术博文:医疗大模型在放射科的可信度验证实践
MedGemma X-Ray技术博文:医疗大模型在放射科的可信度验证实践 1. 引言:当AI走进放射科,我们如何相信它? 想象一下,一位放射科医生每天要面对上百张X光片,每一张都需要仔细查看、分析、撰写报告。长时间高…...
119. 使用 Fluentd concat 过滤器插件在牧场日志中串接多行日志
Situation 地理位置Logs of multiple lines are separated across multiple log events within Pod logs and there is a need to combine them into a single event before forwarding them to a logging solution. 多行日志在 Pod 日志中被分隔在多个日志事件中,…...
10080-基于单片机的智能输液监测系统设计(仿真工程文件+原理图工程+源代码工程+详细介绍说明书)
基于单片机的智能输液监测系统设计(仿真工程文件原理图工程 10080-基于单片机的智能输液监测系统设计(仿真工程文件原理图工程源代码工程详细介绍说明书) 功能描述: (1)设计一个光电传感器,置于一次性输液器的漏斗外边…...
解放B站缓存:m4s-converter让你的视频资产重获自由
解放B站缓存:m4s-converter让你的视频资产重获自由 【免费下载链接】m4s-converter 一个跨平台小工具,将bilibili缓存的m4s格式音视频文件合并成mp4 项目地址: https://gitcode.com/gh_mirrors/m4/m4s-converter 穿透格式迷雾:解码m4s…...
终极指南:如何使用Rust构建企业级数据脱敏系统
终极指南:如何使用Rust构建企业级数据脱敏系统 在当今数据驱动的时代,企业面临着日益严格的隐私保护法规和数据安全挑战。数据脱敏作为保护敏感信息的关键技术,正成为企业数据治理的核心环节。本文将详细介绍如何利用Rust这一安全高效的系统编…...
Unity资源提取工具AssetStudio完全指南:从问题解决到专业应用
Unity资源提取工具AssetStudio完全指南:从问题解决到专业应用 【免费下载链接】AssetStudio AssetStudio - Based on the archived Perfares AssetStudio, I continue Perfares work to keep AssetStudio up-to-date, with support for new Unity versions and addi…...
终极指南:3分钟完成Axure RP中文界面切换,免费语言包全解析
终极指南:3分钟完成Axure RP中文界面切换,免费语言包全解析 【免费下载链接】axure-cn Chinese language file for Axure RP. Axure RP 简体中文语言包。支持 Axure 11、10、9。不定期更新。 项目地址: https://gitcode.com/gh_mirrors/ax/axure-cn …...
VisualCppRedist AIO:一站式解决Windows软件运行依赖问题的终极指南
VisualCppRedist AIO:一站式解决Windows软件运行依赖问题的终极指南 【免费下载链接】vcredist AIO Repack for latest Microsoft Visual C Redistributable Runtimes 项目地址: https://gitcode.com/gh_mirrors/vc/vcredist 你是否曾经遇到过这样的情况&…...
告别烧录失败!深度解析迪文T5L串口屏(DMG80480T070_05WTR)工程配置与文件系统的那些‘潜规则’
告别烧录失败!深度解析迪文T5L串口屏工程配置与文件系统的那些‘潜规则’ 当你第一次拿到DMG80480T070_05WTR这款迪文T5L串口屏时,可能会被它强大的功能所吸引——200MHz双核CPU、24bit真彩色显示、支持多种UI元素和二次开发能力。但很快,你就…...
OBS模糊插件终极指南:如何用obs-composite-blur提升直播画面专业度
OBS模糊插件终极指南:如何用obs-composite-blur提升直播画面专业度 【免费下载链接】obs-composite-blur A comprehensive blur plugin for OBS that provides several different blur algorithms, and proper compositing. 项目地址: https://gitcode.com/gh_mir…...
