【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数组中寻找没有遍历的结点，在进行一次深度优先或者广度优先。也就是要在原来的代码上在套一层。

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Personality Enhanced Emotion Generation Modeling for Dialogue Systems

Personality Enhanced Emotion Generation Modeling for Dialogue Systems

对话系统的人格增强情绪生成建模 摘要1 介绍2 相关工作2.1 个性、情感和情绪2.2 个性的理论模型2.3 在对话系统中整合个性情感建模 3 方法3.1 任务定义3.2 个性增强型情感生成模型3.3 情感状态推理单元3.3.1 情绪遗忘机制3.3.2 情感调节机制 3.4 训练 4 实验4.1 数据集 PELD 摘…
阅读更多...
C语言基础(三)——指针

C语言基础(三)——指针

五、指针 5.1 指针的定义 内存区域中的每字节都对应一个编号&#xff0c;这个编号就是“地址”. 在程序中定义一个变量&#xff0c;在对程序进行编译时&#xff0c;系统就会给这个变量分配内存单元. 按变量地址存取变量值的方式称为“直接访问”&#xff0c;如printf("&…
阅读更多...
C++ 入门（八）— 常量和字符串

C++ 入门（八）— 常量和字符串

常量和字符串 常量变量常量表达式编译时优化 Constexpr 变量std::string字符串输出 std::coutstd::string可以处理不同长度的字符串字符串输入 std::cin用于输入文本std::getline()不要按值传递Constexpr 字符串 std::string_view可以使用许多不同类型的字符串进行初始化可以接…
阅读更多...
基于springboot+html实现的衣物捐赠平台

基于springboot+html实现的衣物捐赠平台

一、系统架构 前端&#xff1a;html | layui | jquery | css 后端&#xff1a;springboot | thymeleaf | mybatis 环境&#xff1a;jdk1.8 | mysql | maven 二、代码及数据库 三、功能介绍 01. 登录页 02. 注册 03. web页-首页 04. web页-捐赠衣服 05. web页-论坛交流…
阅读更多...
Doris实战——金融壹账通指标中台的应用实践

Doris实战——金融壹账通指标中台的应用实践

目录 前言 一、业务痛点 二、早期架构挑战 三、架构升级 四、一体化指标数据平台 4.1 构建指标体系 4.2 构建指标平台功能 五、Doris指标应用实践 六、未来规划 原文大佬的这篇指标中台的应用实践有借鉴意义&#xff0c;这里摘抄下来用作学习和知识沉淀。 前言 在搭建…
阅读更多...
开源项目_代码生成项目介绍

开源项目_代码生成项目介绍

1 CodeGeeX 系列 1.1 CodeGeeX 项目地址&#xff1a;https://github.com/THUDM/CodeGeeX 7.6k Star主要由 Python 编写深度学习框架是 Mindspore代码约 2.5W 行有 Dockerfile&#xff0c;可在本地搭建环境模型大小为 150 亿参数相对早期的代码生成模型&#xff0c;开放全部代…
阅读更多...
BAT等大厂必问技术面试题，2024Android开发面试解答之设计模式

BAT等大厂必问技术面试题，2024Android开发面试解答之设计模式

IT行业薪水高&#xff0c;这是众所周知的&#xff0c;所以很多人大学都选择IT相关专业&#xff0c;即使非该专业的人&#xff0c;毕业了也想去一个培训机构镀镀金&#xff0c;进入这一行业。 但是有关这个行业35岁就退休的说法&#xff0c;也一直盛传。 加上这几年不断有各大…
阅读更多...
基于java Springboot实现课程评分系统设计和实现

基于java Springboot实现课程评分系统设计和实现

基于java Springboot实现课程评分系统设计和实现 博主介绍&#xff1a;多年java开发经验&#xff0c;专注Java开发、定制、远程、文档编写指导等,csdn特邀作者、专注于Java技术领域 作者主页 央顺技术团队 Java毕设项目精品实战案例《1000套》 欢迎点赞 收藏 ⭐留言 文末获取源…
阅读更多...
【白嫖8k买的机构vip教程】Appium自动化(3)：Appium-Desktop界面介绍

【白嫖8k买的机构vip教程】Appium自动化(3)：Appium-Desktop界面介绍

Appium-Desktop主界面包含三个菜单Simple、Advanced、Presets Simple界面&#xff1a; Host设置Appium server的ip地址&#xff0c;本地调试可以将ip地址修改为127.0.0.1&#xff1b;Port设置端口号&#xff0c;默认是4723不用修改Start Server 启动 Appium serverEdit Confi…
阅读更多...
网络安全课程VIP介绍（比同行便宜）

网络安全课程VIP介绍（比同行便宜）

免责声明 本文发布的工具和脚本&#xff0c;仅用作测试和学习研究&#xff0c;禁止用于商业用途&#xff0c;不能保证其合法性&#xff0c;准确性&#xff0c;完整性和有效性&#xff0c;请根据情况自行判断。如果任何单位或个人认为该项目的脚本可能涉嫌侵犯其权利&#xff0c…
阅读更多...
（学习日记）2024.03.01：UCOSIII第三节

（学习日记）2024.03.01：UCOSIII第三节

写在前面&#xff1a; 由于时间的不足与学习的碎片化&#xff0c;写博客变得有些奢侈。 但是对于记录学习&#xff08;忘了以后能快速复习&#xff09;的渴望一天天变得强烈。 既然如此 不如以天为单位&#xff0c;以时间为顺序&#xff0c;仅仅将博客当做一个知识学习的目录&a…
阅读更多...
Java毕业设计-基于springboot开发的私人健身与教练预约系统-毕业论文+答辩PPT（有源代码）

Java毕业设计-基于springboot开发的私人健身与教练预约系统-毕业论文+答辩PPT（有源代码）

文章目录 前言一、毕设成果演示&#xff08;源代码在文末&#xff09;二、毕设摘要展示1.开发说明2.需求分析3、系统功能结构 三、系统实现展示1、系统功能模块2、后台功能模块2.1管理员功能2.2用户功能2.3教练功能 四、毕设内容和源代码获取总结 [Java毕业设计-基于springboot…
阅读更多...
零拷贝技术深入分析

零拷贝技术深入分析

一、零拷贝 在前面的文章“深浅拷贝、COW及零拷贝”中对零拷贝进行过分析&#xff0c;但没有举例子&#xff0c;也没有深入进行展开分析。本文将结合实际的例程对零拷贝进行更深入的分析和说明。 在传统的IO操作中&#xff0c;以文件通过网络传输为例 &#xff0c;一般会经历以…
阅读更多...
【前端素材】推荐优质在线花卉商城电商网页Flowery平台模板（附源码）

【前端素材】推荐优质在线花卉商城电商网页Flowery平台模板（附源码）

一、需求分析 1、系统定义 在线花卉商城是一个通过互联网提供花卉销售服务的电子商务平台&#xff0c;用户可以在该平台上浏览、选择和购买各种花卉产品。 2、功能需求 在线花卉商城是一个通过互联网提供花卉销售服务的电子商务平台&#xff0c;用户可以在该平台上浏览、选…
阅读更多...
内存取证 Volatility

内存取证 Volatility

文章目录 安装工具volatility和插件mimikatz[陇剑杯 2021]内存分析 内存分析工具 volatility&#xff0c;有Volatility2和Volatility3两种&#xff0c;分别基于Python2和Python3环境运行。说是一般Volatility2比Volatility3好用&#xff0c;所以我也选择的Volatility2版本。 一…
阅读更多...
kubectl 陈述式资源管理方法

kubectl 陈述式资源管理方法

目录 陈述式资源管理方法 项目的生命周期 1.创建kubectl create命令 2.发布kubectl expose命令 service的4的基本类型 查看pod网络状态详细信息和 Service暴露的端口 查看关联后端的节点 ​编辑 查看 service 的描述信息 ​编辑在 node01 节点上操作&#xff0c;查看…
阅读更多...
LeetCode 2120.执行所有后缀指令

LeetCode 2120.执行所有后缀指令

现有一个 n x n 大小的网格&#xff0c;左上角单元格坐标 (0, 0) &#xff0c;右下角单元格坐标 (n - 1, n - 1) 。给你整数 n 和一个整数数组 startPos &#xff0c;其中 startPos [startrow, startcol] 表示机器人最开始在坐标为 (startrow, startcol) 的单元格上。 另给你…
阅读更多...
前端的文字的字体应该如何设置

前端的文字的字体应该如何设置

要设置文字的字体&#xff0c;在CSS中使用font-family属性。这个属性可以接受一个或多个字体名称作为其值&#xff0c;浏览器会按照列表中的顺序尝试使用这些字体渲染文本。如果第一个字体不可用&#xff0c;浏览器会尝试使用列表中的下一个字体&#xff0c;依此类推。 字体设…
阅读更多...
SpringCloud gateway限流无效,redis版本低的问题

SpringCloud gateway限流无效,redis版本低的问题

在使用springCloud gateway的限流功能的时候&#xff0c;配置RedisRateLimiter限流无效&#xff0c;后来发现是Redis版本过低导致的问题&#xff0c;实测 Redis版本为3.0.504时限流无效&#xff0c;改用7.0.x版本的Redis后限流生效。查了资料发现很多人都遇见过这个问题&#x…
阅读更多...
让面试官眼前一黑，手把手带你打造个性化的 GitHub 首页

让面试官眼前一黑，手把手带你打造个性化的 GitHub 首页

前期回顾 手机打开 第三方 “微信、快手、QQ、电话、信息” 等-CSDN博客https://blog.csdn.net/m0_57904695/article/details/136304084?spm1001.2014.3001.5501 &#x1f6a9;Github访问 Huo-zai-feng-lang-li (彩色之外) (github.com) &…
阅读更多...
最新文章

Copyright @ 2022~2023