【数据结构】图的广度优先遍历
一.广度优先遍历的基本思想
(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中设置。利用图形化方式或命令行查看或设置网卡。本文仅初步讨论添加、查看与删除网卡,有关…...
2025届学术党必备的六大降重复率平台实际效果
Ai论文网站排名(开题报告、文献综述、降aigc率、降重综合对比) TOP1. 千笔AI TOP2. aipasspaper TOP3. 清北论文 TOP4. 豆包 TOP5. kimi TOP6. deepseek 人工智能生成内容也就是AIGC普及之后,文本检测系统变得越来越精密了。为了避免机…...
禅道最新22.0+ 手动删除无法安装之清理卸载办法
禅道项目管理软件卸载方法详解:如何彻底清除所有相关文件和配置在企业或个人开发环境中,禅道(Zentao)作为一款广受欢迎的开源项目管理工具,因其功能全面、易用性强而被广泛使用。然而,在某些情况下…...
2.5m双馈风力发电机DFIG的带储能Simulink电气建模与仿真(参数源自IEEE3)”
2.5m双馈风力发电机DFIG并网_带储能的simulink电气建模与仿真,参数来自IEEE3半夜两点盯着Simulink界面眼冒绿光,手里的咖啡已经续到第五杯——这大概每个搞风电建模的工程师都经历过的场景。今天咱们就唠唠这个让人又爱又恨的2.5MW双馈风机并网模型&…...
颠覆式Alienware设备控制:500KB轻量工具实现10倍性能提升与个性化体验
颠覆式Alienware设备控制:500KB轻量工具实现10倍性能提升与个性化体验 【免费下载链接】alienfx-tools Alienware systems lights, fans, and power control tools and apps 项目地址: https://gitcode.com/gh_mirrors/al/alienfx-tools 当你启动Alienware电…...
javaweb广告服务型互联网平台
目录同行可拿货,招校园代理 ,本人源头供货商功能模块划分广告主功能代理商功能平台管理功能技术架构要点扩展功能项目技术支持源码获取详细视频演示 :文章底部获取博主联系方式!同行可合作同行可拿货,招校园代理 ,本人源头供货商 功能模块划分 广告服务…...
告别繁琐配置:用快马ai一键生成windows版openclaw自动化安装脚本原型
最近在折腾一个开源工具OpenClaw,发现它在Windows下的安装过程真是让人头大——各种依赖检查、环境变量配置,手动操作一不小心就出错。作为一个懒人程序员,我决定用Python写个自动化安装脚本,结果发现用InsCode(快马)平台的AI辅助…...
游戏脚本助手,电脑点击器,脚本自动点击识图找图_无限试用版
熊猫精灵脚本助手 分类功能项其他功能管理、插件、生成、中控、进程守护、护盾配置、坐标工具脚本设置窗口设置、绑定设置、运行设置、变量设置、程序设置图色识别Yolo识别、找图识别、点色找色文字识别ocr识别找字、字库识别、验证码识别键鼠操作鼠标操作、键盘操作、录制脚本…...
新手福音:用快马生成centos8下载安装全流程可视化引导工具
今天想和大家分享一个特别适合Linux新手的实用工具——用InsCode(快马)平台快速生成CentOS 8下载安装引导程序。作为一个从Windows转Linux的过来人,我深知第一次面对系统安装时的茫然,这个工具能帮你把复杂流程变成可视化指引。 为什么需要这个工具 刚接…...
终极优化指南:NodeSource Node.js 二进制分发版的 Docker 镜像体积与启动速度革命
终极优化指南:NodeSource Node.js 二进制分发版的 Docker 镜像体积与启动速度革命 【免费下载链接】distributions NodeSource Node.js Binary Distributions 项目地址: https://gitcode.com/gh_mirrors/di/distributions NodeSource Node.js 二进制分发版为…...
homelab健康检查:Kubernetes探针配置与最佳实践
homelab健康检查:Kubernetes探针配置与最佳实践 引言 在homelab环境中,Kubernetes集群的稳定性至关重要。健康检查是保障服务稳定运行的关键机制,通过配置适当的探针,可以及时发现并处理容器故障,提高系统的可靠性和…...
