＜高阶数据结构＞图

图

  • 必要概念
    • 大致用途
  • 存图
    • 邻接矩阵
    • 邻接表
  • 遍历
    • BFS(广度优先)
    • DFS(深度优先)
  • 最小生成树
    • Kruskal算法
    • Prim算法
  • 寻最短路径
    • Dijkstra算法

必要概念

图根据有无方向分为，有向图和无向图
组成：G = (V, E)

  • 顶点集合 V
  • 边的集合 E
    G(Graph),V(Vertex),E(Edge)
    图可以说是一个灰常抽象且学习比较有挑战性的一个数据结构，一个图是由顶点集合和边集合组成的

大致用途

  • 表示交通网络图，例如，顶点是城市，边是城市之间的距离
  • 表示社交关系图

存图

一般存储我们有两种方法

邻接矩阵

  • 采用vector保存顶点
  • 采用矩阵(二维数组)保存边
    在这里插入图片描述

优点：

  1. 非常适合存储稠密图
  2. O(1)判断两个顶点的连接关系，并取得权值

缺点：

  1. 相对而言不适合用来查找一个顶点连接的所有边O(N)
template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
class Graph
{
public:
	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)
	{
		auto it = _indexMap.find(v);
		if (it != _indexMap.end())
		{
			return it->second;
		}
		else
		{
			//assert(false);
			throw std::invalid_argument("顶点不存在");

			return -1;
		}
	}

	void _AddEdge(size_t srci, size_t dsti, const W& w)
	{
		// 无向图
		if (Direction == false)
		{
			_matrix[srci][dsti] = w;
			_matrix[dsti][srci] = w;
		}
		else
		{
			_matrix[srci][dsti] = w;
		}
	}

	void AddEdge(const V& src, const V& dst, const W& w)
	{
		{
			size_t srci = GetVertexIndex(src);
			size_t dsti = GetVertexIndex(dst);

			_AddEdge(srci, dsti, w);
		}
	}

	void Print()
	{
		// 打印顶点
		for (size_t i = 0; i < _vertexs.size(); ++i)
		{
			cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
		}
		cout << endl;

		cout << "  ";
		for (size_t i = 0; i < _matrix.size(); ++i)
		{
			//cout << i << " ";
			printf("%-4d", i);
		}
		cout << endl;

		// 打印矩阵
		for (size_t i = 0; i < _matrix.size(); ++i)
		{
			cout << i << " "; // 竖下标
			for (size_t j = 0; j < _matrix.size(); ++j)
			{
				//cout << _matrix[i][j] << " ";
				if (_matrix[i][j] == MAX_W)
				{
					//cout << "* ";
					printf("%-4c", '*');
				}
				else
				{
					//cout << _matrix[i][j] << " ";
					printf("%-4d", _matrix[i][j]);
				}
			}
			cout << endl;
		}
		cout << endl;
	}
	}

private:
	std::vector<V> _vertexs;		// 顶点集合
	std::map<V, int> _indexMap;		// 顶点对应的下标关系
	std::vector<std::vector<W>> _matrix; // 邻接矩阵
};

邻接表

  • 使用vector保存所有的顶点
  • 使用链表保存与每个顶点连通的顶点

优点：

  1. 适合存储稀疏图
  2. 适合查找一个顶点连接的边

缺点：

  1. 不适合去确定两个顶点是否相连及权值

namespace link_table
{
	template<class W>
	struct Edge
	{
		int _dsti; // 目标点的下标
		W _w; // 权值
		Edge* _next;

		Edge(int dsti, const W& w)
			:_dsti(dsti)
			,_w(w)
			,_next(nullptr)
		{

		}
	};

	template<class V, class W, bool Direction = false>
	class Graph
	{
		typedef Edge<W> Edge;
	public:
		// 图的创建
		// 1.IO输入 -- 不方便测试 OJ适合
		// 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;
			}

			_tables.resize(n, nullptr);
		}

		size_t GetVertexIndex(const V& v)
		{
			auto it = _indexMap.find(v);
			if (it != _indexMap.end())
			{
				return it->second;
			}
			else
			{
				//assert(false);
				throw std::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);

				// 1->2
				Edge* eg = new Edge(dsti, w);
				eg->_next = _tables[srci];
				_tables[srci] = eg;
				// 如果是无向图 2->1
				if (Direction == false)
				{
					Edge* eg = new Edge(srci, w);
					eg->_next = _tables[dsti];
					_tables[dsti] = eg;
				}
			}
		}

		void Print()
		{
			// 打印顶点
			for (size_t i = 0; i < _vertexs.size(); ++i)
			{
				cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
			}
			cout << endl;

			for (size_t i = 0; i < _tables.size(); ++i)
			{
				cout << _vertexs[i] << "[" << i << "]->";
				Edge* cur = _tables[i];
				while (cur)
				{
					cout << _vertexs[cur->_dsti] << "[" << cur->_dsti << " : " << cur->_w << "]" << "->";
					cur = cur->_next;
				}
				cout << "nullptr" << endl;
			}
		}

	private:
		std::vector<V> _vertexs;		// 顶点集合
		std::map<V, int> _indexMap;		// 顶点对应的下标关系
		std::vector<Edge*> _tables; // 邻接表
	};
	        
	void TestGraph1()
	{
		Graph<char, int, 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();
	}
}

遍历

BFS(广度优先)

以某一顶点为起点，一层一层的向外遍历
在这里插入图片描述
我们只需借助一个队列来辅助实现，这里我们先将A入队列，在A出队列的时候，将A连通的最近一层B,C,D入队列，B出队列时将E入队列，如此运行直到队列为空时，遍历结束，出队列顺序即时我们的遍历次序
为了防止B出队列时，再次将A和C入队列，可以开一个标记容器，标记入了队列的顶点

void BFS(const V& src)
{
	size_t srci = GetVertexIndex(src);
	// 队列和标记数组
	std::queue<int> q;
	std::vector<bool> visited(_vertexs.size(), false);

	q.push(srci);
	visited[srci] = true;
	int levelSize = 1;

	while (!q.empty())
	{
		// 一层一层出
		for (size_t i = 0; i < levelSize; ++i)
		{
			int front = q.front();
			q.pop();
			cout << front << ":" << _vertexs[front] << " ";
			// 把front的邻接顶点入队列
			for (size_t i = 0; i < _vertexs.size(); ++i)
			{
				if (_matrix[front][i] != MAX_W)
				{
					if (visited[i] != true)
					{
						q.push(i);
						visited[i] = true;
					}
				}
			}
			cout << endl;
		}
		levelSize = q.size();
	}

	cout << endl;
}

DFS(深度优先)

以某一顶点为起点，深度优先遍历
在这里插入图片描述


void _DFS(size_t srci, std::vector<bool>& visited)
{
	cout << srci << ":" << _vertexs[srci] << endl;
	visited[srci] = true;

	// 找一个srci相邻的没有访问过的点，去往深度遍历	
	for (size_t i = 0; i < _vertexs.size(); ++i)
	{
		if (_matrix[srci][i] != MAX_W && visited[i] == false)
		{
			_DFS(i, visited);
		}
	}
}

void DFS(const V& src)
{
	size_t srci = GetVertexIndex(src);
	std::vector<bool> visited(_vertexs.size(), false);

	_DFS(srci, visited);
}

最小生成树

  • 构成生成树这些边加起来权值是最小的
    这里采用两种算法，两种算法都采取了贪心的策略

Kruskal算法

方法
每次找权值最小边，注意这个最小边不能构成环，将所有顶点连接起来结束算法
可以借助一个并查集结构，用于判断已选的边是否构成环
这个算法是看的局部最优边，只关注局部最优
下图是算法笔记这本书里面的算法流程图
在这里插入图片描述
定义个Edge边结构，辅助算法

struct Edge
{
	size_t _srci;
	size_t _dsti;
	W _w;

	Edge(size_t srci, size_t dsti, const W& w)
		:_srci(srci)
		, _dsti(dsti)
		, _w(w)
	{

	}

	bool operator>(const Edge& e) const 
	{  
		return _w > e._w;
	}
};

W Kruskal(Self& minTree)
{
	// 初始化minTree
	size_t n = _matrix.size();
	minTree._vertexs = _vertexs;
	minTree._indexMap = _indexMap;
	minTree._matrix.resize(n);
	for (size_t i = 0; i < n; ++i)
	{
		minTree._matrix[i].resize(n, MAX_W);
	}

	std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge >> minque;
	for (size_t i = 0; i < _matrix.size(); ++i)
	{
		for (size_t j = 0; j < _matrix[i].size(); ++j)
		{
			if (j > i && _matrix[i][j] != MAX_W)
			{
				minque.push(Edge(i, j, _matrix[i][j]));
			}
		}
	}

	//选出n-1条边
	W totalw = 0;
	int size = 0;
	UnionFindSet ufs(_matrix.size());
	while (!minque.empty())
	{
		Edge eg = minque.top();
		minque.pop();

		if (!ufs.InSet(eg._srci, eg._dsti))
		{
			cout << _vertexs[eg._srci] << "->" << _vertexs[eg._dsti] << endl;
			minTree._AddEdge(eg._srci, eg._dsti, eg._w);
			ufs.Union(eg._srci, eg._dsti);
			++size;
			totalw += eg._w;
		}
	}

	if (size == n - 1)
		return totalw;
	else
		return -1;
}

Prim算法

方法
从某一顶点开始，选择该顶点连接的边中权值最小的边，再到下一顶点选连接的边中最小权值的边，同样需要记录一下已经选过了的顶点
借助一个队列实现，和广度优先遍历方法有点类似，只不过这里只需要选择最小权值边的顶点

int Prim(Self& minTree, const V& src)
		{
			size_t srci = GetVertexIndex(src);
			size_t n = _vertexs.size();
			// 初始化minTree
			minTree._vertexs = _vertexs;
			minTree._indexMap = _indexMap;
			minTree._matrix.resize(n);
			for (size_t i = 0; i < n; ++i)
			{
				minTree._matrix[i].resize(n, MAX_W);
			}

			vector<bool> visited(n, false);
			std::priority_queue < Edge, std::vector<Edge>, std::greater<Edge >> pq;

			for (size_t i = 0; i < n; ++i)
			{
				if (_matrix[srci][i] != MAX_W)
				{
					pq.push(Edge(srci, i, _matrix[srci][i]));
				}
			}
			
			size_t size = 0;
			visited[srci] = true;
			int total = 0;
			while (!pq.empty())
			{
				Edge front = pq.top();
				pq.pop();

				if (visited[front._dsti] == true)
				{
					continue;
				}

				cout << _vertexs[front._srci] << "->" << _vertexs[front._dsti] << endl;
				minTree._AddEdge(front._srci, front._dsti, front._w);

				if (size == n -1)
				{
					break;
				}
				
				// 入队列
				for (size_t i = 0; i < n; ++i)
				{
					if (visited[i] != true && _matrix[front._dsti][i] != MAX_W)
					{
						pq.push(Edge(front._dsti, i, _matrix[front._dsti][i]));
					}
				}

				++size;
				total += front._w;
				visited[front._dsti] = true;
			}

			return total;
		}

寻最短路径

找某个顶点到图中另一顶点走的最短路径

Dijkstra算法

使用的也是贪心的策略

  • 将选择了的顶点和没有选择的顶点分为两个集合
  • dist记录从s顶点到Q顶点的最短路径权值和
  • pPath记录满足最短路径时每个顶点的上一个顶点下标
  • 定义一个S数组记录已经确定的最短顶点，一旦选定不可更改
    下图
  1. 起始，s到s的最短路径权值和为0，dist[0]=0,上一个顶点为s下标为0，pPath[0]=0
  2. s起点,s到y的最短路径权值和为5. dist[1]=5,pPath[1]=0,s到t的最短路径权值和为10,dist[3]=10,pPath[3]=0
  3. 选权值最小的y作为起点,s通过y到t的最短路径权值和为8. 8 < 10, 更新dist[3]=8,pPath[3]=1,s通过y到x最短路径权值和为14,dist[4]=14,pPath[4]=1, ,s通过y到z最短路径权值和为7,dist[2]=7,pPath[4]=1,
    在这里插入图片描述
void PrintShortPath(const V& src, const vector<int>& dist, const vector<int>& parentPath)
{
	size_t N = _vertexs.size();
	size_t srci = GetVertexIndex(src);
	for (size_t i = 0; i < N; ++i)
	{
		if (i == srci)
			continue;

		vector<int> path;
		int parenti = i;
		while (parenti != srci)
		{
			path.push_back(parenti);
			parenti = parentPath[parenti];
		}
		path.push_back(srci);
		reverse(path.begin(), path.end());
		for (auto pos : path)
		{
			cout << _vertexs[pos] << "->";
		}
		cout << dist[i] << endl;
	}
}

void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath)
{
	size_t srci = GetVertexIndex(src);
	size_t n = _vertexs.size();

	dist.resize(n, MAX_W);
	pPath.resize(n, -1);

	dist[srci] = W();
	pPath[srci] = 0;

	vector<bool> s(n, false);

	for (size_t i = 0; i < n; ++i)
	{
		W min = MAX_W;
		size_t u = srci;
		for (size_t j = 0; j < n; ++j)
		{
			if (s[j] != true && dist[j] < min)
			{
				min = dist[j];
				u = j;
			}
		}

		// 松弛算法
		for (size_t k = 0; k < n; ++k)
		{
			if (s[u] == false && _matrix[u][k] != MAX_W
				&& dist[u] + _matrix[u][k] < dist[k])
			{
				dist[k] = dist[u] + _matrix[u][k];
				pPath[k] = u;
			}
		}
		s[u] = true;

	}
}

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

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

相关文章

Docker容器：docker consul的注册与发现及consul-template

Docker容器：docker consul的注册与发现及consul-template

Docker容器&#xff1a;docker consul的注册与发现及consul-template守护进程 一.docker consul的注册与发现介绍 1.什么是服务注册与发现 &#xff08;1&#xff09;服务注册与发现是微服务架构中不可或缺的重要组件。 &#xff08;2&#xff09;为解决服务都是单节点的&a…
阅读更多...
李沐pytorch学习-BatchNormalization

李沐pytorch学习-BatchNormalization

一、意义 在使用较深的网络时&#xff0c;BatchNormalization&#xff08;批量归一化&#xff09;几乎是必需的&#xff0c;可以加速收敛。 对于图1所示的全连接层神经网络&#xff0c;输出节点的GroundTruth为&#xff0c;损失函数为&#xff0c;则损失对权重的梯度为&#xf…
阅读更多...
接口测试总结分享（http与rpc）

接口测试总结分享（http与rpc）

接口测试是测试系统组件间接口的一种测试。接口测试主要用于检测外部系统与系统之间以及内部各个子系统之间的交互点。测试的重点是要检查数据的交换&#xff0c;传递和控制管理过程&#xff0c;以及系统间的相互逻辑依赖关系等。 一、了解一下HTTP与RPC 1. HTTP&#xff08;H…
阅读更多...
YOLOv5屏蔽区域检测（选择区域检测）

YOLOv5屏蔽区域检测（选择区域检测）

YOLOv5屏蔽区域检测以及选择区域检测 前期准备labelme选择mask区域 代码改动 前期准备 思路就是通过一个mask掩膜&#xff0c;对我们想要屏蔽或者选择的区域进行遮挡处理&#xff0c;在推理的时候&#xff0c;将有mask掩膜的图像输入&#xff0c;将最后的结果显示在原始图像上…
阅读更多...
【Go 基础篇】Go语言中的自定义错误处理

【Go 基础篇】Go语言中的自定义错误处理

错误是程序开发过程中不可避免的一部分&#xff0c;而Go语言以其简洁和高效的特性闻名。在Go中&#xff0c;自定义错误&#xff08;Custom Errors&#xff09;是一种强大的方式&#xff0c;可以为特定应用场景创建清晰的错误类型&#xff0c;以便更好地处理和调试问题。本文将详…
阅读更多...
基于微信小程序的汽车租赁系统的设计与实现ljx7y

基于微信小程序的汽车租赁系统的设计与实现ljx7y

汽车租赁系统&#xff0c;主要包括管理员、用户二个权限角色&#xff0c;对于用户角色不同&#xff0c;所使用的功能模块相应不同。本文从管理员、用户的功能要求出发&#xff0c;汽车租赁系统系统中的功能模块主要是实现管理员后端&#xff1b;首页、个人中心、汽车品牌管理、…
阅读更多...
算法通关村十三关 | 进制转换问题处理模板

算法通关村十三关 | 进制转换问题处理模板

1. 七进制数 题目&#xff1a;LeetCode504&#xff1a;504. 七进制数 - 力扣&#xff08;LeetCode&#xff09; 思路 进制转换&#xff0c;对几转换就是对几求余&#xff0c;最后将所有的余数反过来即可、如果num< 0&#xff0c;先取绝对值&#xff0c;再进行操作。 100转7…
阅读更多...
MYSQL表的增删改查（单表）

MYSQL表的增删改查（单表）

文章目录 一、CRUD二、creat(新增)三、查询&#xff08;Retrieve&#xff09;四、修改&#xff08;update&#xff09;五、删除&#xff08;Delete&#xff09; 一、CRUD SQL 最核心的就是增删改查&#xff0c;后端开发工作中&#xff0c;遇到的最核心的操作也是这个 二、creat…
阅读更多...
2023高教社杯数学建模思路 - 复盘：人力资源安排的最优化模型

2023高教社杯数学建模思路 - 复盘：人力资源安排的最优化模型

文章目录 0 赛题思路1 描述2 问题概括3 建模过程3.1 边界说明3.2 符号约定3.3 分析3.4 模型建立3.5 模型求解 4 模型评价与推广5 实现代码 建模资料 0 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 1 描述 …
阅读更多...
Blazor 依赖注入妙用：巧设回调

Blazor 依赖注入妙用：巧设回调

文章目录 前言依赖注入特性需求解决方案示意图 前言 依赖注入我之前写过一篇文章&#xff0c;没看过的可以看看这个。 C# Blazor 学习笔记(10):依赖注入 依赖注入特性 只能Razor组件中注入所有Razor组件在作用域注入的都是同一个依赖。作用域可以看看我之前的文章。 需求 …
阅读更多...
string类中的一些问题

string类中的一些问题

前言&#xff1a;C中的string类是继承C语言的字符数组的字符串来实现的&#xff0c;其中包含许多C的字符串的相关知识的同时&#xff0c;也蕴含很多的类与对象的相关知识&#xff0c;在面试中&#xff0c;面试官总喜欢让学生自己来模拟实现string类&#xff0c;最主要是实现str…
阅读更多...
azure data studio SQL扩展插件开发笔记

azure data studio SQL扩展插件开发笔记

node.js环境下拉取脚手架 npm install -g yo generator-azuredatastudio yo azuredatastudio 改代码 运行 调试扩展&#xff0c;在visual studio code中安装插件即可 然后visual studio code打开进行修改运行即可 image.png 运行后自动打开auzre data studio了&#xff0c; 下面…
阅读更多...
开源与专有软件：比较与对比

开源与专有软件：比较与对比

&#x1f337;&#x1f341; 博主猫头虎 带您 Go to New World.✨&#x1f341; &#x1f984; 博客首页——猫头虎的博客&#x1f390; &#x1f433;《面试题大全专栏》 文章图文并茂&#x1f995;生动形象&#x1f996;简单易学&#xff01;欢迎大家来踩踩~&#x1f33a; &a…
阅读更多...
中文乱码处理

中文乱码处理

&#x1f600;前言 中文乱码处理 &#x1f3e0;个人主页&#xff1a;尘觉主页 &#x1f9d1;个人简介&#xff1a;大家好&#xff0c;我是尘觉&#xff0c;希望我的文章可以帮助到大家&#xff0c;您的满意是我的动力&#x1f609;&#x1f609; 在csdn获奖荣誉: &#x1f3c…
阅读更多...
kubernetes deploy standalone mysql demo

kubernetes deploy standalone mysql demo

kubernetes 集群内部署 单节点 mysql ansible all -m shell -a "mkdir -p /mnt/mysql/data"cat mysql-pv-pvc.yaml apiVersion: v1 kind: PersistentVolume metadata:name: mysql-pv-volumelabels:type: local spec:storageClassName: manualcapacity:storage: 5Gi…
阅读更多...
JVM第一篇 认识java虚拟机

JVM第一篇 认识java虚拟机

目录 1. 什么是java虚拟机 2. java虚拟机分类 2.1. 商用虚拟机 2.2. 嵌入式虚拟机 3.java虚拟机架构 4.java虚拟机运行过程 1. 什么是java虚拟机 传统意义上的虚拟机是一种抽象化的计算机&#xff0c;通过在实际的计算机上仿真模拟各种计算机功能来实现的&#xff0c;是操…
阅读更多...
数据结构入门 — 链表详解_单链表

数据结构入门 — 链表详解_单链表

前言 数据结构入门 — 单链表详解* 博客主页链接&#xff1a;https://blog.csdn.net/m0_74014525 关注博主&#xff0c;后期持续更新系列文章 文章末尾有源码 *****感谢观看&#xff0c;希望对你有所帮助***** 系列文章 第一篇&#xff1a;数据结构入门 — 链表详解_单链表 第…
阅读更多...
突破边界：文本检测算法的革新与应用前景

突破边界：文本检测算法的革新与应用前景

突破边界&#xff1a;文本检测算法的革新与应用前景 1.文本检测理论篇&#xff08;文本检测方法介绍&#xff09; 文本检测任务是找出图像或视频中的文字位置。不同于目标检测任务&#xff0c;目标检测不仅要解决定位问题&#xff0c;还要解决目标分类问题。 文本在图像中的…
阅读更多...
使用EventLog Analyzer 进行路由器监控

使用EventLog Analyzer 进行路由器监控

路由器是任何计算机网络的构建块&#xff0c;引导网络中的流量&#xff0c;管理员需要确保路由器已配置并正常工作&#xff0c;以确保网络安全。 监控路由器中的用户活动 在网络安全方面&#xff0c;与路由器相关的风险是一个严重的问题。具有松散安全策略的网络使入侵者可以…
阅读更多...
Flutter实现StackView

Flutter实现StackView

1.让界面之间可以嵌套且执行动画。 2.界面的添加遵循先进后出原则。 3.需要使用AnimateView&#xff0c;请看我上一篇博客。 演示&#xff1a; 代码&#xff1a; Stack: import package:flutter/cupertino.dart;///栈&#xff0c;先进后出 class KqWidgetStack {final Lis…
阅读更多...
最新文章

Copyright @ 2022~2023