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

news/2024/4/15 16:54:26

文章目录

  • 一、图的遍历
  • 二、广度优先遍历
    • 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.mrgr.cn/p/26615374

相关文章

从 iOS 设备恢复数据的 20 个iOS 数据恢复工具

作为 iPhone、iPad 或 iPod 用户&#xff0c;您可能普遍担心自己可能会丢失存储在珍贵 iOS 设备中的所有宝贵数据。数据丢失的原因多种多样&#xff0c;这里列出了一些常见原因&#xff1a; 1. iOS 软件更新 2. 恢复出厂设置 3. 越狱 4. 误操作删除数据 5. iOS 设备崩溃 …

使用openai-whisper实现语音转文字

使用openai-whisper实现语音转文字 1 安装依赖 1.1 Windows下安装ffmpeg FFmpeg是一套可以用来记录、转换数字音频、视频&#xff0c;并能将其转化为流的开源计算机程序。采用LGPL或GPL许可证。它提供了录制、转换以及流化音视频的完整解决方案。 # ffmpeg官网 https://ffm…

WhatsApp代理設置指南

某些情況下&#xff0c;你可能需要使用WhatsApp代理來確保WhatsApp順暢且不受限制的通信。本篇文章將講解WhatsApp代理是什麼、WhatsApp代理的使用場景、以及如何在WhatsApp中使用和設置代理。​​​​​​​ WhatsApp代理指什麼? WhatsApp代理是位於可以訪問WhatsApp的國家或…

多输入多输出 | Matlab实现RIME-BP霜冰算法优化BP神经网络多输入多输出预测

多输入多输出 | Matlab实现RIME-BP霜冰算法优化BP神经网络多输入多输出预测 目录 多输入多输出 | Matlab实现RIME-BP霜冰算法优化BP神经网络多输入多输出预测预测效果基本介绍程序设计往期精彩参考资料 预测效果 基本介绍 多输入多输出 | Matlab实现RIME-BP霜冰算法优化BP神经网…

《汇编语言》- 读书笔记 - 第13章-int 指令

《汇编语言》- 读书笔记 - 第13章-int 指令 13.1 int 指令13.2 编写供应用程序调用的中断例程中断例程&#xff1a;求一 word 型数据的平方主程序中断处理程序执行效果 中断例程&#xff1a;将一个全是字母&#xff0c;以0结尾的字符串&#xff0c;转化为大写主程序中断处理程序…

【C++】C++的四种强制类型转换

1、C语言中的类型转换 在C语言中&#xff0c;如果赋值运算符左右两侧类型不同&#xff0c;或者形参与实参类型不匹配&#xff0c;或者返回值类型与接收返回值类型不一致时&#xff0c;就需要发生类型转化&#xff0c;C语言中总共有两种形式的类型转换&#xff1a;隐式类型转换…

mysql,for循环执行sql

遇到一个问题&#xff0c;我需要模拟上百万数据来优化sql&#xff0c;线上数据down不下来&#xff0c;测试库又没有&#xff0c;写代码执行要么慢要么就是sql语句太长。 于是&#xff0c;直接用mysql自带的功能去实现&#xff01; 简单而简单 mysql可以for循环&#xff1f;没…

Docker技术概论(4):Docker CLI 基本用法解析

Docker技术概论&#xff08;4&#xff09; Docker CLI 基本用法解析 - 文章信息 - Author: 李俊才 (jcLee95) Visit me at: https://jclee95.blog.csdn.netMy WebSite&#xff1a;http://thispage.tech/Email: 291148484163.com. Shenzhen ChinaAddress of this article:http…

Spring AI上架

Spring AI 来了 Spring AI 是 AI 工程师的一个应用框架,它提供了一个友好的 API 和开发 AI 应用的抽象,旨在简化 AI 应用的开发工序。 提供对常见模型的接入能力,目前已经上架 https://start.spring.io/,提供大家测试访问。(请注意虽然已经上架 start.spring.io,但目前还…

文件基础和文件fd

文章目录 预备知识C语言的文件接口系统调用文件fd 正文开始前给大家推荐个网站&#xff0c;前些天发现了一个巨牛的 人工智能学习网站&#xff0c; 通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。 点击跳转到网站。 预备知识 我们平时说文件就是说文件里…

cyi青少年CTF擂台挑战赛 2024 #Round 1 wp

cyi青少年CTF擂台挑战赛 2024 #Round 1 wpWEB EasyMD5 靶机真不敢恭维 一个文件上传界面,得上传pdf传两个pdfhttps://www.cnblogs.com/wysngblogs/p/15905398.html 这篇文章看到md5碰撞,找到个工具fastcoll_v1.0.0.5 https://www.win.tue.nl/hashclash/后续写的wp,flag可能…

Gitlab Runner自动推送Docker映像

接上文,增加两个stage 最简单的推送,其实是在docker build后边带上--push的开关即可。 但是不经过测试就上传,Docker仓库里很快会堆满垃圾。 所以我们设计新增两个场景,经过测试之后才push映像去仓库。 stages:- build-docker-image- test- push-image variables:PAY_IMAGE…

黑马JavaWeb课程中安装vue脚手架出现的问题

1 安装node.js 要想前端工程化&#xff0c;必须安装node.js&#xff0c;前端工程化的环境。 在成功安装node.js后&#xff0c; 修改全局包安装路径为Node.js安装目录&#xff0c; 修改npm镜像源为淘宝镜像源&#xff0c;这里出现第一个问题&#xff0c;视频中给的淘宝镜像为&…

python实现常见一元随机变量的概率分布

一. 随机变量 随机变量是一个从样本空间 Ω \Omega Ω到实数空间 R R R的函数&#xff0c;比如随机变量 X X X可以表示投骰子的点数。随机变量一般可以分为两类&#xff1a; 离散型随机变量&#xff1a;随机变量的取值为有限个。连续型随机变量&#xff1a;随机变量的取值是连…

关于Windows 10的兼容模式,看这篇文章就够了

这篇文章解释了如何使用Windows兼容模式在Windows 10上完美地运行旧版本的Windows程序。 如何更改Windows 10兼容模式设置 如果疑难解答没有完成任务&#xff0c;并且你知道该程序以前使用过哪个版本的Windows&#xff0c;则可以手动更改Windows 10兼容模式的设置&#xff1a…

Spring-自动配置

自动配置流程细节梳理: 1、导入starter-web:导入了web开发场景1、场景启动器导入了相关场景的所有依赖:starter-json、starter-tomcat、springmvc 2、每个场景启动器都引入了一个spring-boot-starter,核心场景启动器。(上面三个也有) 3、核心场景启动器引入了spring-boot-a…

[回归指标]R2、PCC(Pearson’s r )

R2相关系数 R2相关系数很熟悉了&#xff0c;就不具体解释了。 皮尔逊相关系数&#xff08;PCC&#xff09; 皮尔逊相关系数是研究变量之间线性相关程度的量&#xff0c;R方和PCC是不同的指标。R方衡量x和y的接近程度&#xff0c;PCC衡量的是x和y的变化趋势是否相同。R方是不…

《TCP/IP详解 卷一》第9章 广播和组播

目录 9.1 引言 9.2 广播 9.2.1 使用广播地址 9.2.2 发送广播数据报 9.3 组播 9.3.1 将组播IP地址转换为组播MAC地址 9.3.2 例子 9.3.3 发送组播数据报 9.3.4 接收组播数据报 9.3.5 主机地址过滤 9.4 IGMP协议和MLD协议 9.4.1 组成员的IGMP和MLD处理 9.4.2 组播路由…

Gitlab Runner自动制作C#网站项目的Docker映像

概述 代码签入Gitlab后,Gitlab Runner自动执行docker build,构建网站应用的Docker映像。 在Visual Studio 2022中创建解决方案在Gitlab中创建项目 这一步省略。 签入源代码到Gitlab为项目添加Dockerfile在解决方案根目录下创建“.gitlab-ci.yml” stages:- build-docker-imag…

Docker容器(3)单容器管理

一、单容器 1.1概念简介 Docker三个重要概念: 仓库(Repository); 镜像(Image); 容器(Container). *Docker的三个重要概念是仓库(Repository)、镜像(Image)和容器(Container)**。具体如下&#xff1a; **镜像(Image)**&#xff1a;Docker镜像是创建容器的基础&#xff0c;它类似…