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

【数据结构】图的广度优先遍历

一.广度优先遍历的基本思想

(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;}}}
}

四.总结

广度优先:确定起始节点后,全部邻接点(分支)同时开始遍历;

深度优先:先从一个邻接点(分支)开始遍历,直至该分支全部遍历完成,再遍历按顺序的下一个分支。

相关文章:

【数据结构】图的广度优先遍历

一.广度优先遍历的基本思想 &#xff08;1&#xff09;访问顶点v&#xff1b; &#xff08;2&#xff09;依次访问v的各个未被访问的邻接点v1&#xff0c;v2&#xff0c;v3……&#xff0c;vk&#xff1b; &#xff08;3&#xff09;分别从v1&#xff0c;v2&#xff0c;v3……...

AM@函数展开成幂级数@间接法@常用麦克劳林幂级数展开公式

文章目录 间接法推导幂级数展开常用麦克劳林幂级数展开公式应用例例例 间接法推导幂级数展开 已知函数的幂级数展开公式间接推导其他函数幂级数 使用原始的推导公式推导函数的幂级数展开是繁琐不便的,需要分别计算各项系数 a n f ( n ) ( 0 ) n ! a_{n}\frac{f^{(n)}(0)}{n!}…...

LeetCode994.腐烂的橘子

看完题我觉得这不是和上一道岛屿的题一样简单嘛&#xff0c;然后写了将近2个小时才写出来&#xff0c;我的思路就是&#xff0c;用check()先对grid检查一下&#xff0c;是否有以下情况&#xff1a; &#xff08;如果有1的周围都是空&#xff0c;则这个位置用不腐烂&#xff0c;…...

【开源】基于Vue和SpringBoot的康复中心管理系统

项目编号&#xff1a; S 056 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S056&#xff0c;文末获取源码。} 项目编号&#xff1a;S056&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 普通用户模块2.2 护工模块2.3 管理员…...

【音视频基础】AVI文件格式

AVI文件采用的是RIFF文件结构方式。波形音频wave&#xff0c;MIDI和数字视频AVI都采用这种格式存储。 AVI文件的整体结构如下图所示 构造RIFF文件的基本单元叫做数据块&#xff08;Chunk&#xff09;&#xff0c;每个数据块包含3个部分 4字节的数据块标记&#xff08;或者叫…...

图书馆整理I(从尾到头打印列表),剑指offer,力扣

目录 题目地址&#xff1a; 我们直接看题解吧&#xff1a; 解题方法&#xff1a; 难度分析&#xff1a; 审题目事例提示&#xff1a; 解题思路(辅助栈)&#xff1a; 代码&#xff08;递归&#xff09;&#xff1a; 代码&#xff08;列表插入&#xff09;&#xff1a; 相似题目对…...

C++编写的多线程自动爬虫程序

目录 引言 一、程序的设计 二、程序的实现 三、程序的测试 四、优化与改进 五、代码示例 总结 引言 随着互联网的快速发展&#xff0c;网络爬虫程序已经成为数据采集、信息处理的重要工具。C作为一种高效的编程语言&#xff0c;具有高效的并发处理能力和丰富的网络编程…...

SMB信息泄露的利用

一、背景 今天分享SMB信息泄露&#xff0c;SMB&#xff08;Server Message Block&#xff09;网络通信协议&#xff0c;早些时候被用于Web链接和客户端与服务器之间的信息通信&#xff0c;现在大部分Web页面使用HTTP协议&#xff0c;在web领域应用较少。另一方面SMB协议还是被…...

QT自定义信号,信号emit,信号参数注册

qt如何自定义信号 使用signals声明返回值是void在需要发送信号的地方使用 emit 信号名字(参数)进行发送 在需要链接的地方使用connect进行链接 ct进行链接...

06.webpack性能优化--构建速度

优化babel-loaderhappyPackIgnorePluginparalleUglifyPluginnoParse自动刷新 1 happypack多进程打包 js单线程&#xff0c;开启多进程打包提高构建速度&#xff08;特别是多核CPU&#xff09; const HappyPack require(happypack)module.exports smart(webpackCommonConf,…...

11-15 周三 softmax 回归学习

11-15 周三 softmax 回归学习 时间版本修改人描述2023年11月15日11:17:27V0.1宋全恒新建文档 简介 softmax分享可以参考什么是softmax 回归估计一个连续值&#xff0c;分类预测一个离散类别。 恶意软件的判断 回归和分类 分类可以认为从回归的单输出变成多输出 B站学习 softm…...

React新手必懂的知识点

react思想&#xff1a;组件化开发 React 的核心概念是组件化开发&#xff0c;将用户界面拆分成独立的可复用组件。学习如何创建和使用 React 组件&#xff0c;以及组件之间的数据传递和通信是非常重要的。 React的思想就是拆分组件与使用组件。 import React from react;// 定…...

es为什么这么快

es为什么这么快的方式 es的基于Lucene开源搜索引擎&#xff0c;负责文件存储和搜索&#xff0c;支持http请求&#xff0c;以json形式展示 这样介绍你有可能有点迷糊我们详细解释 es 使用的倒排索引的方式&#xff0c;进行数据存储方式&#xff0c;给每一个字段创建索引&…...

Pandas分组聚合_Python数据分析与可视化

Pandas分组聚合 分组单列和多列分组Series 系列分组通过数据类型或者字典分组获取单个分组对分组进行迭代 聚合应用单个聚合函数应用多个聚合函数自定义函数传入 agg() 中对不同的列使用不同的聚合函数 分组聚合的流程主要有三步&#xff1a; 分割步骤将 DataFrame 按照指定的…...

VMware17虚拟机Linux安装教程(详解附图,带VMware Workstation 17 Pro安装)

一、安装 VMware 附官方下载链接&#xff08;VM 17 pro&#xff09;&#xff1a;https://download3.vmware.com/software/WKST-1701-WIN/VMware-workstation-full-17.0.1-21139696.exe 打开下载好的VMware Workstation 17 Pro安装包&#xff1b; 点击下一步&#xff1b; 勾选我…...

基于SDN技术构建多平面业务承载网络

随着企业数字化的浪潮席卷各个行业&#xff0c;传统网络架构面临着更为复杂和多样化的挑战。企业正在寻找一种全面适应数字化需求的网络解决方案。随着软件定义网络&#xff08;SDN&#xff09;的发展&#xff0c;“多业务SDN一张网”解决方案为企业提供了一种全新的网络架构&a…...

关于卓越服务的调研报告

NetSuite知识会发起的本次调研从2023年11月2日开始&#xff0c;到11月12日结束。16日已向参与调研的朋友邮件回复&#xff0c;感谢您的付出&#xff01;今朝分享此报告&#xff0c;各位同学参考。 调研问题与反馈总结 问题1&#xff1a;您能想到哪些服务组织能够提供高满意度&…...

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/ 目录&#xff1a; cd /etc/apt/ 3、备份默认源文件 sudo cp sources.list sources.list_bak 4、编…...

03. Python中的语句

1、前言 在《Python基础数据类型》一文中&#xff0c;我们了解了Python中的基础数据类型&#xff0c;今天我们继续了解下Python中的语句和函数。 2、语句 在Python中常用的语句可以大致分为两类&#xff1a;条件语句、循环语句。 2.1、条件语句 条件语句就是我们编码时常见…...

Linux CentOS7 添加网卡

一台主机中安装多块网卡&#xff0c;有许多优势。可以实现多项功能。 为了学习网卡参数的设置&#xff0c;可以为主机添加多块网卡。与添加磁盘一样&#xff0c;要在VMware中设置。利用图形化方式或命令行查看或设置网卡。本文仅初步讨论添加、查看与删除网卡&#xff0c;有关…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...