【C++从0到王者】第四十六站:图的深度优先与广度优先

文章目录

  • 一、图的遍历
  • 二、广度优先遍历
    • 1.思想
    • 2.算法实现
    • 3.六度好友
  • 三、深度优先遍历
    • 1.思想
    • 2.代码实现
  • 四、其他问题

一、图的遍历

对于图而言,我们的遍历一般是遍历顶点,而不是边,因为边的遍历是比较简单的,就是邻接矩阵或者邻接表里面的内容。而对于遍历顶点就稍微有点麻烦了。

给定一个图G和其中任意一个顶点v0,从v0出发,沿着图中各边访问图中的所有顶点,且每个顶点仅被遍历一次。"遍历"即对结点进行某种操作的意思。

树以前前是怎么遍历的,此处可以直接用来遍历图吗?为什么?

树以前的遍历有深度优先(先序、中序、后序)和广度优先遍历(层序遍历)两种

图也是类似的。

二、广度优先遍历

1.思想

下面是广度优先遍历的一个比较形象的例子

image-20240219162241498

对于下面的图而言,也是类似的,先去找A,然后去遍历A的周围的三个结点,然后遍历这三个结点的周围结点,一层一层往外遍历,最终遍历完所有的结点,需要注意的是不要重复遍历了!

image-20240219162326247

2.算法实现

我们这里用邻接矩阵来实现我们的代码。如下代码所示。

namespace matrix
{//V代表顶点, W是weight代表权值,MAX_W代表权值的最大值,Direction代表是有向图还是无向图,flase表示无向template<class V, class W, W Max_W = INT_MAX, bool Direction = false>class Graph{public://图的创建//1. IO输入 不方便测试//2. 图结构关系写到文件,读取文件//3. 手动添加边Graph(const V* a, size_t n){_vertexs.reserve(n);for (size_t i = 0; i < n; i++){_vertexs.push_back(a[i]);_indexMap[a[i]] = i;}_matrix.resize(n);for (size_t i = 0; i < _matrix.size(); i++){_matrix[i].resize(n, Max_W);}}size_t GetVertexIndex(const V& v){//return _indexMap[v];auto it = _indexMap.find(v);if (it != _indexMap.end()){return it->second;}else{//assert(false)throw invalid_argument("顶点不存在");return -1;}}void AddEdge(const V& src, const V& dst, const W& w){size_t srci = GetVertexIndex(src);size_t dsti = GetVertexIndex(dst);_matrix[srci][dsti] = w;if (Direction == false){_matrix[dsti][srci] = w;}}void Print(){for (size_t i = 0; i < _vertexs.size(); i++){cout << "[" << i << "]" << "->" << _vertexs[i] << endl;}cout << endl;cout << "   ";for (int i = 0; i < _vertexs.size(); i++){//cout << _vertexs[i] << " ";printf("%-3d ", i);}cout << endl;for (size_t i = 0; i < _matrix.size(); i++){//cout << _vertexs[i] << " ";printf("%d ", i);for (size_t j = 0; j < _matrix[i].size(); j++){if (_matrix[i][j] == INT_MAX){cout << " * " << " ";}else{printf("%-3d ", _matrix[i][j]);//cout << _matrix[i][j] << " ";}}cout << endl;}}void BFS(const V& src){int srci = GetVertexIndex(src);queue<int> q; //广度遍历的队列vector<bool> visited(_vertexs.size(), false); //标记数组q.push(srci); //起点入队visited[srci] = true; //已经被遍历过了while (!q.empty()){int front = q.front();q.pop();cout << front << ":" << _vertexs[front] << endl;//把front顶点的邻接顶点入队列for (size_t i = 0; i < _matrix[front].size(); i++){if (_matrix[front][i] != Max_W){if (visited[i] == false){q.push(i);visited[i] = true;}}}}} private:vector<V> _vertexs; //顶点集合map<V, int> _indexMap; //顶点对应的下标关系vector<vector<W>> _matrix; //临界矩阵};

在上面的代码当中,这个图的如下所示

image-20240219171331165

在BFS的时候,我们使用一个队列和一个标记数组来解决。

我们先将第一个起点入队,并且进行标记已经被遍历了,然后像二叉树的层序遍历一样,一层一层去寻找它的周围结点。由于我们用的是邻接矩阵,那么我们就可以以出队列的这个结点为起点,遍历邻接矩阵的对应行,找到满足的进行入队列,然后依次进行标记。从而最终可以遍历整个图

最终结果为

image-20240219171940093

3.六度好友

如下面的题目就是一个简单的广度优先遍历

image-20240219162459971

这道题与二叉树中求出第几层的元素是十分类似的。就是层序遍历,不过要打印出第六层的结果

void BFSLevel(const V& src)
{int srci = GetVertexIndex(src);queue<int> q; //广度遍历的队列vector<bool> visited(_vertexs.size(), false); //标记数组q.push(srci); //起点入队visited[srci] = true; //已经被遍历过了int levelSize = 1;while (!q.empty()){for (int i = 0; i < levelSize; i++){int front = q.front();q.pop();cout << front << ":" << _vertexs[front] << " ";//把front顶点的邻接顶点入队列for (size_t i = 0; i < _matrix[front].size(); i++){if (_matrix[front][i] != Max_W){if (visited[i] == false){q.push(i);visited[i] = true;}}}}cout << endl;levelSize = q.size();}
}
void TestGraphBDFS()
{string a[] = { "张三", "李四", "王五", "赵六", "周七" };Graph<string, int> g1(a, sizeof(a) / sizeof(string));g1.AddEdge("张三", "李四", 100);g1.AddEdge("张三", "王五", 200);g1.AddEdge("王五", "赵六", 30);g1.AddEdge("王五", "周七", 30);g1.Print();g1.BFS("张三");cout << endl;g1.BFSLevel("张三");
}

这里我们用一个循环来记录每层的个数,每打印够一层就换行。如上代码所示

运行结果为

image-20240219174014273

三、深度优先遍历

1.思想

image-20240219180359909

如上是深度优先的一个形象的案例,下面是深度优先在一个图中的实际场景

image-20240219180429488

我们可以看到,他就像二叉树的先序遍历一样,一直走到最深层,然后退回去。这里需要注意的就是要进行标记已经遍历过的结点

2.代码实现

如下是深度优先的代码实现

namespace matrix
{//V代表顶点, W是weight代表权值,MAX_W代表权值的最大值,Direction代表是有向图还是无向图,flase表示无向template<class V, class W, W Max_W = INT_MAX, bool Direction = false>class Graph{public://图的创建//1. IO输入 不方便测试//2. 图结构关系写到文件,读取文件//3. 手动添加边Graph(const V* a, size_t n){_vertexs.reserve(n);for (size_t i = 0; i < n; i++){_vertexs.push_back(a[i]);_indexMap[a[i]] = i;}_matrix.resize(n);for (size_t i = 0; i < _matrix.size(); i++){_matrix[i].resize(n, Max_W);}}size_t GetVertexIndex(const V& v){//return _indexMap[v];auto it = _indexMap.find(v);if (it != _indexMap.end()){return it->second;}else{//assert(false)throw invalid_argument("顶点不存在");return -1;}}void AddEdge(const V& src, const V& dst, const W& w){size_t srci = GetVertexIndex(src);size_t dsti = GetVertexIndex(dst);_matrix[srci][dsti] = w;if (Direction == false){_matrix[dsti][srci] = w;}}void Print(){for (size_t i = 0; i < _vertexs.size(); i++){cout << "[" << i << "]" << "->" << _vertexs[i] << endl;}cout << endl;cout << "   ";for (int i = 0; i < _vertexs.size(); i++){//cout << _vertexs[i] << " ";printf("%-3d ", i);}cout << endl;for (size_t i = 0; i < _matrix.size(); i++){//cout << _vertexs[i] << " ";printf("%d ", i);for (size_t j = 0; j < _matrix[i].size(); j++){if (_matrix[i][j] == INT_MAX){cout << " * " << " ";}else{printf("%-3d ", _matrix[i][j]);//cout << _matrix[i][j] << " ";}}cout << endl;}}void BFS(const V& src){int srci = GetVertexIndex(src);queue<int> q; //广度遍历的队列vector<bool> visited(_vertexs.size(), false); //标记数组q.push(srci); //起点入队visited[srci] = true; //已经被遍历过了while (!q.empty()){int front = q.front();q.pop();cout << front << ":" << _vertexs[front] << endl;//把front顶点的邻接顶点入队列for (size_t i = 0; i < _matrix[front].size(); i++){if (_matrix[front][i] != Max_W){if (visited[i] == false){q.push(i);visited[i] = true;}}}}} void BFSLevel(const V& src){int srci = GetVertexIndex(src);queue<int> q; //广度遍历的队列vector<bool> visited(_vertexs.size(), false); //标记数组q.push(srci); //起点入队visited[srci] = true; //已经被遍历过了int levelSize = 1;while (!q.empty()){for (int i = 0; i < levelSize; i++){int front = q.front();q.pop();cout << front << ":" << _vertexs[front] << " ";//把front顶点的邻接顶点入队列for (size_t i = 0; i < _matrix[front].size(); i++){if (_matrix[front][i] != Max_W){if (visited[i] == false){q.push(i);visited[i] = true;}}}}cout << endl;levelSize = q.size();}}void _DFS(size_t srci, vector<bool>& visited){cout << srci << ":" << _vertexs[srci] << endl;visited[srci] = true;for (int i = 0; i < _matrix[srci].size(); i++){if (_matrix[srci][i] != Max_W && visited[i] == false){_DFS(i, visited);}}}void DFS(const V& src){int srci = GetVertexIndex(src);vector<bool> visited(_vertexs.size(), false);_DFS(srci, visited);}private:vector<V> _vertexs; //顶点集合map<V, int> _indexMap; //顶点对应的下标关系vector<vector<W>> _matrix; //临界矩阵};void TestGraph(){Graph<char, int, INT_MAX, true> g("0123", 4);g.AddEdge('0', '1', 1);g.AddEdge('0', '3', 4);g.AddEdge('1', '3', 2);g.AddEdge('1', '2', 9);g.AddEdge('2', '3', 8);g.AddEdge('2', '1', 5);g.AddEdge('2', '0', 3);g.AddEdge('3', '2', 6);g.Print();}void TestGraphBDFS(){string a[] = { "张三", "李四", "王五", "赵六", "周七" };Graph<string, int> g1(a, sizeof(a) / sizeof(string));g1.AddEdge("张三", "李四", 100);g1.AddEdge("张三", "王五", 200);g1.AddEdge("王五", "赵六", 30);g1.AddEdge("王五", "周七", 30);g1.Print();g1.BFS("张三");cout << endl;g1.BFSLevel("张三");cout << endl;g1.DFS("张三");}}

像先序遍历一样,这里也是需要一个子函数比较好的,因为我们需要使用递归,让子函数去进行递归是最好的

运行结果如下所示

image-20240219180714110

四、其他问题

关于深度优先和广度优先,上面的清空自然是很理想的情况。并且由于起点不同,深度优先和广度优先的结果是不同的。但是有时候,也会出现下面的问题。

比如图不连通的问题。也就是图存在孤立的结点。那么这样的话,以某个点为起点就没有遍历完成

这里我们可以有个解决方案是从visited数组中寻找没有遍历的结点,在进行一次深度优先或者广度优先。也就是要在原来的代码上在套一层。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/266945.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

electron+vue3全家桶+vite项目搭建【28】封装窗口工具类【2】窗口组,维护窗口关系

文章目录 引入实现效果思路主进程模块渲染进程模块测试效果 引入 demo项目地址 窗口工具类系列文章&#xff1a; 封装窗口工具类【1】雏形 我们思考一下窗口间的关系&#xff0c;窗口创建和销毁的一些动作&#xff0c;例如父子窗口&#xff0c;窗口组合等等&#xff0c;还有…

无字母数字rce总结(自增、取反、异或、或、临时文件上传)

目录 自增 取反 异或 或 临时文件上传 自增 自 PHP 8.3.0 起&#xff0c;此功能已软弃用 在 PHP 中&#xff0c;可以递增非数字字符串。该字符串必须是字母数字 ASCII 字符串。当到达字母 Z 且递增到下个字母时&#xff0c;将进位到左侧值。例如&#xff0c;$a Z; $a;将…

Day07:基础入门-抓包技术全局协议封包监听网卡模式APP小程序PC应用

目录 非HTTP/HTTPS协议抓包工具 WireShark 科来网络分析系统 WPE封包 思维导图 章节知识点&#xff1a; 应用架构&#xff1a;Web/APP/云应用/三方服务/负载均衡等 安全产品&#xff1a;CDN/WAF/IDS/IPS/蜜罐/防火墙/杀毒等 渗透命令&#xff1a;文件上传下载/端口服务/Sh…

强大而灵活的python装饰器

装饰器&#xff08;Decorators&#xff09; 一、概述 在Python中&#xff0c;装饰器是一种特殊类型的函数&#xff0c;它允许我们修改或增强其他函数的功能&#xff0c;而无需修改其源代码。装饰器在函数定义之后立即调用&#xff0c;并以函数对象作为参数。装饰器返回一个新…

【前端素材】推荐优质在线高端家具电商网页Classi平台模板(附源码)

一、需求分析 1、系统定义 在线高端家具商城是一个专门销售高端家具产品的电子商务平台&#xff0c;旨在为消费者提供购买高品质家具的便捷渠道。 2、功能需求 在线高端家具商城是一个专门销售高端家具产品的电子商务平台&#xff0c;旨在为消费者提供购买高品质家具的便捷…

p18 线性代数,行阶梯型矩阵

行阶梯型矩阵 行最简型矩阵

Golang Redis:构建高效和可扩展的应用程序

利用Redis的闪电般的数据存储和Golang的无缝集成解锁协同效应 在当前的应用程序开发中&#xff0c;高效的数据存储和检索的必要性已经变得至关重要。Redis&#xff0c;作为一个闪电般快速的开源内存数据结构存储方案&#xff0c;为各种应用场景提供了可靠的解决方案。在这份完…

安防视频监控EasyCVR平台使用GB28181协议接入时,如何正确配置端口?

国标GB28181协议EasyCVR安防视频监控平台可以提供实时远程视频监控、视频录像、录像回放与存储、告警、语音对讲、云台控制、平台级联、磁盘阵列存储、视频集中存储、云存储等丰富的视频能力&#xff0c;平台支持7*24小时实时高清视频监控&#xff0c;能同时播放多路监控视频流…

Docker 第十九章 : 阿里云个人镜像仓使用

Docker 第十九章 : 阿里云个人镜像仓使用 本章知识点: 如何创建镜像库,如何设置密码,如何登录与退出个人镜像仓,如何本地打镜像,如何将本地镜像推送到个人镜像库。 背景 在项目YapiDocker部署中,因读取mongo:latest 版本不一致,导致后续执行步骤的异常。遇到此场景…

深度学习 精选笔记(8)梯度消失和梯度爆炸

学习参考&#xff1a; 动手学深度学习2.0Deep-Learning-with-TensorFlow-bookpytorchlightning ①如有冒犯、请联系侵删。 ②已写完的笔记文章会不定时一直修订修改(删、改、增)&#xff0c;以达到集多方教程的精华于一文的目的。 ③非常推荐上面&#xff08;学习参考&#x…

TP6上传图片到OSS(记录贴)

1&#xff0c;先安装&#xff0c;我使用composer安装 在项目的根目录运行composer require aliyuncs/oss-sdk-php 2,安装成功以后vendor目录下可以看到如图&#xff1a; 3&#xff0c;上传图片代码如下&#xff1a; <?php namespace app\controller;use app\BaseControll…

文件拖放到窗体事件

网上的实现1 实现结果 具体实现代码&#xff1a;注意需要使能允许拖拽 public partial class Form1 : Form {public Form1(){InitializeComponent();this.AllowDrop true; //允许拖拽}private void Form1_DragEnter(object sender, DragEventArgs e){this.Text DateTime.No…

Vue中<style scoped lang=“scss“>的含义

这段代码中的<style scoped lang"scss">是HTML和Vue框架结合使用时常见的一个模式&#xff0c;具体含义如下&#xff1a; scoped&#xff1a;这是一个Vue.js特有的属性&#xff0c;用来指定样式只应用于当前组件的元素。没有这个属性时&#xff0c;样式会全局应…

[unity] c# 扩展知识点其一 【个人复习笔记/有不足之处欢迎斧正/侵删】

.NET 微软的.Net既不是编程语言也不是框架,是类似于互联网时代、次时代、21世纪、信息时代之类的宣传口号,是一整套技术体系的统称&#xff0c;或者说是微软提供的技术平台的代号. 1.跨语言 只要是面向.NET平台的编程语言(C#、VB、 C、 F#等等)&#xff0c;用其中一种语言编写…

电脑休眠之后唤不醒

现象&#xff1a;午休时间电脑休眠了&#xff0c;醒来之后发现在密码输入界面&#xff0c;但鼠标键盘没反应。按重启键或电源机重新开机&#xff0c;结果开不了机。 原因&#xff1a;1、内存条脏了&#xff0c;导致内存条读取失败 2、休眠的时候硬盘休眠了&#xff0c;导致按…

基于java+springboot动物检疫信息管理系统设计和实现

基于java SSM springboot动物检疫信息管理系统设计和实现 博主介绍&#xff1a;多年java开发经验&#xff0c;专注Java开发、定制、远程、文档编写指导等,csdn特邀作者、专注于Java技术领域 作者主页 央顺技术团队 Java毕设项目精品实战案例《1000套》 欢迎点赞 收藏 ⭐留言 文…

fly-barrage 前端弹幕库(3):滚动弹幕的设计与实现

项目官网地址&#xff1a;https://fly-barrage.netlify.app/&#xff1b; &#x1f451;&#x1f40b;&#x1f389;如果感觉项目还不错的话&#xff0c;还请点下 star &#x1f31f;&#x1f31f;&#x1f31f;。 Gitee&#xff1a;https://gitee.com/fei_fei27/fly-barrage&a…

【QT+QGIS跨平台编译】之五十一:【QGIS_CORE跨平台编译】—【qgsexpressionparser.cpp生成】

文章目录 一、Bison二、生成来源三、构建过程一、Bison GNU Bison 是一个通用的解析器生成器,它可以将注释的无上下文语法转换为使用 LALR (1) 解析表的确定性 LR 或广义 LR (GLR) 解析器。Bison 还可以生成 IELR (1) 或规范 LR (1) 解析表。一旦您熟练使用 Bison,您可以使用…

【MySQL | 第一篇】undo log、redo log、bin log三者之间的区分?

undo log、redo log、bin log三者之间的区分&#xff1f; 从 产生的时间点、日志内容、用途 三方面展开论述即可 1.undo log——撤销日志 时间点&#xff1a;事务开始之前产生&#xff0c;根据当前版本的数据生成一个undo log&#xff0c;也保存在事务开始之前 作用&#xf…

动态规划课堂3-----简单多状态问题(买卖股票最佳时机)

目录 引入&#xff1a; 例题1&#xff1a;按摩师&#xff08;打家劫舍I&#xff09; 例题2&#xff1a;打家劫舍II 例题3&#xff1a;删除并获得点数 例题4&#xff1a;粉刷房子 例题5&#xff1a;买卖股票的最佳时机含冷冻 结语&#xff1a; 引入&#xff1a; 相信看到…