数据结构 —— 图的遍历

news/2024/7/8 1:44:54 标签: 数据结构, 算法

数据结构 —— 图的遍历

  • BFS（广度遍历）
  • 一道美团题
  • DFS（深度遍历）

我们今天来看图的遍历，其实都是之前在二叉树中提过的方法，深度和广度遍历。

在这之前，我们先用一个邻接矩阵来表示一个图：

#pragma once
#include<iostream>
#include<vector>
#include<map>
using namespace std;

//图的模板化
namespace matrix
{
	template<class V, class W, W MAX_W, bool Direction = false>
	class Graph
	{
	public:
		Graph(const V* vertex, size_t n)
		{
			//开辟空间
			_vertex.reserve(n);
			for (int i = 0; i < n; i++)
			{
				_vertex.push_back(vertex[i]);
				_index[vertex[i]] = i;
			}

			//初始化矩阵
			_matrix.resize(n);

			for (auto& e : _matrix)
			{
				e.resize(n, MAX_W);
			}
		}

		//寻找图中的点
		size_t FindSrci(const V& vertex)
		{
			auto ret = _index.find(vertex);

			if (ret != _index.end())
			{
				return ret->second;
			}
			else
			{
				throw invalid_argument("不存在的顶点");
				return -1;
			}
		}

		void _AddEdge(size_t srci, size_t desi, W w)
		{
			_matrix[srci][desi] = w;

			if (Direction == false)
			{
				_matrix[desi][srci] = w;
			}
		}

		//加边
		void AddEdge(const V& srci, const V& desi, W w)
		{
			size_t srcIndex = FindSrci(srci);
			size_t desIndex = FindSrci(desi);

			_AddEdge(srcIndex, desIndex, w);
		}

		void Print()
		{
			//打印标题行
			cout << "      ";
			for (int i = 0; i < _vertex.size(); i++)
			{
				cout << _vertex[i] << " ";
			}
			cout << endl;

			//打印矩阵
			for (int i = 0; i < _vertex.size(); i++)
			{
				cout << _vertex[i] << " ";
				for (int j = 0; j < _matrix[i].size(); j++)
				{
					if (_matrix[i][j] != MAX_W)
					{
						printf("%5d", _matrix[i][j]);
					}
					else
					{
						printf("%5c", '#');
					}
				}
				cout << endl;
			}
		}

	private:
		//存放顶点
		vector<V> _vertex;
		//映射关系
		map<V, size_t> _index;
		//矩阵，图的表示
		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 TestGraph2()
	{
		string a[] = {"海皇","高斯","小傲","小潮","胖迪","小杨","皖皖"};
		Graph<string, int,INT_MAX, false> g1(a, sizeof(a)/sizeof(a[0]));
		g1.AddEdge("小潮", "小傲", 30);
		g1.AddEdge("小潮", "高斯", 83);
		g1.AddEdge("小潮", "海皇", 34);
		g1.AddEdge("胖迪", "海皇", 78);
		g1.AddEdge("胖迪", "小傲", 76);
		g1.AddEdge("小杨", "皖皖", 54);
		g1.AddEdge("小杨", "高斯", 48);

		g1.Print();
	}
}

在这里插入图片描述在这里插入图片描述

BFS（广度遍历）

广度优先遍历和之前二叉树的广度优先遍历一样，我们需要队列来辅助：
在这里插入图片描述我们逻辑上是这张图，但是我们实际遍历的时候，我们遍历的是一个矩阵（二维数组）
在这里插入图片描述因为这个图是联通图，我们从任意一个顶点出发都可以遍历完所有顶点，假设我们从小潮开始：
在这里插入图片描述我们仿照二叉树那里的思路，把相连的节点入队列，把小傲，高斯，海皇入队列：
在这里插入图片描述在矩阵上的表现就是把小潮这一行，不为#的数值的结点入队列：
在这里插入图片描述好，现在有一个问题，假设我现在遍历到了海皇，海皇和小潮相连，按照上面的规则，我们应该把小潮入队列，但是我们一开始就是从小潮开始的，就会造成重复访问，这该则么办呢？

所以在图这里，我们要引入一个数组，标记我们已经访问过的结点，标记过的结点在之后的访问过程中不再入队：

在这里插入图片描述
我们来实现一下：

	void BFS(const V& vertex)
		{
			int vertexIndex = FindSrci(vertex);
			//队列和标记数组
			int n = _vertex.size();
			queue<size_t> q;
			vector<bool> visited(n, false);

			//先入最先访问节点
			q.push(vertexIndex);
			//标记
			visited[vertexIndex] = true;

			while (!q.empty())
			{
				//出队
				size_t front = q.front();
				q.pop();
				cout << _vertex[front] << " ";

				//遍历该行
				for (int i = 0; i < _vertex.size(); i++)
				{
					if (_matrix[front][i] != MAX_W)
					{
						if (visited[i] == false)
						{
							q.push(i);
							visited[i] = true;
						}
					}
				}
				cout << endl;
			}
			
		}

一道美团题

在这里插入图片描述读了题之后，这里让我们计算几度好友，其实我们在BFS已经按照一度二度的顺序打印了，但是我们没有区分，我们区分一下就可以了

void BFS(const V& vertex)
{
    // 获取目标顶点的索引
    int vertexIndex = FindSrci(vertex);
    
    // 初始化队列和标记数组
    int n = _vertex.size();
    queue<size_t> q; // 创建一个队列用于存储待访问的顶点
    vector<bool> visited(n, false); // 创建一个布尔数组，用于标记顶点是否已被访问

    // 将起始顶点添加到队列中，并标记为已访问
    q.push(vertexIndex);
    visited[vertexIndex] = true;

    int levelSize = 1; // 初始化当前层级的顶点数量，初始时只有起始顶点
    int degree = 0; // 初始化度数（即好友的层次）

    // 当队列非空时，继续广度优先搜索
    while (!q.empty())
    {
        // 输出当前度数的好友
        cout << "[" << degree << "]" << "度好友 ";
        
        // 对当前层级的所有顶点进行处理
        for (int j = 0; j < levelSize; j++)
        {
            // 从队列中取出一个顶点
            size_t front = q.front();
            q.pop();
            
            // 输出当前顶点的信息
            cout << _vertex[front] << " ";
            
            // 遍历与当前顶点相邻的所有顶点
            for (int i = 0; i < _vertex.size(); i++)
            {
                // 如果存在一条边连接当前顶点和下一个顶点
                if (_matrix[front][i] != MAX_W)
                {
                    // 如果下一个顶点未被访问过
                    if (!visited[i])
                    {
                        // 将下一个顶点添加到队列中，以便后续访问
                        q.push(i);
                        
                        // 标记下一个顶点为已访问
                        visited[i] = true;
                    }
                }
            }
        }
        
        // 更新下一层级的顶点数量
        levelSize = q.size();
        
        // 换行输出，准备进入下一度数的好友输出
        cout << endl;
        
        // 增加度数计数器
        degree++;
    }
    
    // 最终换行，使输出更清晰
    cout << endl;
}

在这里插入图片描述

DFS（深度遍历）

深度遍历是一条道走到黑：
在这里插入图片描述

// 深度优先搜索的私有辅助函数
void _DFS(size_t vertexIndex, vector<bool>& visited)
{
    // 如果当前顶点尚未访问过
    if (!visited[vertexIndex])
    {
        // 输出当前顶点的值
        cout << _vertex[vertexIndex] << endl;
        
        // 将当前顶点标记为已访问
        visited[vertexIndex] = true;

        // 遍历所有顶点
        for (size_t i = 0; i < _vertex.size(); i++)
        {
            // 如果当前顶点和遍历到的下一个顶点之间存在边，
            // 表示为权重不是最大可能权重（MAX_W），
            // 则对下一个顶点进行深度优先搜索
            if (_matrix[vertexIndex][i] != MAX_W)
                _DFS(i, visited);
        }
    }
}

// 公开的深度优先搜索函数，从给定的顶点开始
void DFS(const V& vertex)
{
    // 查找给定顶点在顶点列表中的索引
    size_t vertexIndex = FindSrci(vertex);
    
    // 初始化一个布尔向量来跟踪每个顶点是否已被访问
    vector<bool> visited(_vertex.size(), false);

    // 调用私有辅助函数进行深度优先搜索
    _DFS(vertexIndex, visited);
}

在这里插入图片描述
（注：本人是小潮院长粉丝，该文章中举的例子不代表真实好友关系，无意挑拨小潮院长内部成员关系，如有冒犯，请不要打我…）

在这里插入图片描述


http://www.niftyadmin.cn/n/5535933.html

相关文章

针对某客户报表系统数据库跑批慢进行性能分析及优化

针对某客户报表系统数据库跑批慢进行性能分析及优化

某客户报表系统数据库跑批时间过长&#xff0c;超出源主库较多&#xff0c;故对其进行了分析调优&#xff0c;目前状态如下&#xff1a; 1、业务连接的rac的scanip&#xff0c;因为负载均衡将跑批的连接连接到了多个计算节点导致节点间通讯成本较高&#xff0c;故速率缓慢&…
阅读更多...
【0292】Postgres内核源码之dynahash 查找实现

【0292】Postgres内核源码之dynahash 查找实现

0. 前言 在【0291】Postgres内核之dynahash table 创建 一文中&#xff0c;从内核源码的实现角度讲解了Postgres创建dynahash的底层实现机制&#xff1b;本文将继续从内核角度分析Postgres dynahash find的实现原理。 1. dynahash find
阅读更多...
Airflow: 大数据调度工具详解

Airflow: 大数据调度工具详解

欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;欢迎订阅相关专栏&#xff1a; 欢迎关注微信公众号&#xff1a;野老杂谈 ⭐️ 全网最全IT互联网公司面试宝典&#xff1a;收集整理全网各大IT互联网公司技术、项目、HR面试真题. ⭐️ AIGC时代的创新与未来&a…
阅读更多...
AR视频技术与EasyDSS流媒体视频管理平台：打造沉浸式视频体验

AR视频技术与EasyDSS流媒体视频管理平台：打造沉浸式视频体验

随着增强现实&#xff08;AR&#xff09;技术的飞速发展&#xff0c;其在各个领域的应用日益广泛。这项技术通过实时计算摄影机影像的位置及角度&#xff0c;将虚拟信息叠加到真实世界中&#xff0c;为用户带来超越现实的感官体验。AR视频技术不仅极大地丰富了我们的视觉体验&a…
阅读更多...
SAP 接口-银行账号主数据维护接口【MDM-＞SAP】开发说明书（包括测试样例、程序代码仅作参考，不保证一定可以运行)

SAP 接口-银行账号主数据维护接口【MDM-＞SAP】开发说明书（包括测试样例、程序代码仅作参考，不保证一定可以运行)

接口映射字段 开发通用说明 根据MDM传输字段调用BAPI生成银行账号及开户行。 开户行维护BAPI【BAPI_BANK_CREATE】 银行账号维护BAPI【BAPI_FCLM_BAM_AMD_BNKANT】 接口字段【ZZZH 主账户标识】=1时字段【DTAAI】DME标识赋值：常用； 接口字段【ZZZH 主账户标识】=0时字段…
阅读更多...
流批一体计算引擎-12-[Flink]旁路输出getSideOutput(OutputTag)实现拆分流和复制流

流批一体计算引擎-12-[Flink]旁路输出getSideOutput(OutputTag)实现拆分流和复制流

官网旁路输出 Flink拆分流和复制流 我们在处理数据的时候，有时候想对不同情况的数据进行不同的处理，那么就需要把流进行拆分或者复制。 如果是使用filter来进行拆分，也能满足我们的需求，但每次筛选都要保留整个流，然后遍历整个流，显然很浪费性能，假如能够在一个流了多次…
阅读更多...
人工智能标准化与AI科技快速进步的矛盾

人工智能标准化与AI科技快速进步的矛盾

人工智能标准化与技术快速进步之间确实存在一定的矛盾&#xff0c;这主要体现在以下几个方面&#xff1a; 快速发展的技术与标准化的稳定性。人工智能技术以其快速的创新和进步而闻名。新的算法、模型和应用不断涌现&#xff0c;但标准化过程需要时间和广泛的共识&#xff0c;这…
阅读更多...
实训项目中用到的一些知识点（部分来自文心一言）

实训项目中用到的一些知识点（部分来自文心一言）

一、使用的注解及其功能 Configuration&#xff1a;用于定义配置类&#xff0c;该类可以包含Bean注解的方法&#xff0c;这些方法将被Spring容器在启动时自动调用&#xff0c;用于声明bean。 EnableSwagger2&#xff1a;启用Swagger 2.x&#xff0c;一个规范和完整的框架&…
阅读更多...
最新文章

Copyright @ 2022~2023