高阶数据结构图下篇

目录:

  • 图的基本概念二
    • 深度优先遍历(DFS)
      • 广度优先遍历(BFS)
  • kruskal(克鲁斯卡尔算法)
    • Prim(普里姆算法)
      • Dijkstra(迪杰斯特拉算法)
        • Bellman-ford(贝尔曼-福特算法)
  • flyod-warshall(佛洛伊德算法)

图的基本概念二

完全图:任意两个顶点之间有且仅有一条边,则称此图为无向完全图;任意两个顶点之间有且仅有方向相反的边,则称此图为有向完全图。

邻接顶点:在无向图G中,若(U,V)是E(G)中的一条边;则称U和V互为邻接顶点,有向图中,则称顶点U邻接到V。

顶点的度:顶点的度是指与它相关联的边的条数,记作deg(V)。

路径:在图G中,若从顶点vi出发有一组边使其可达到顶点vj,则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路径。

路径长度:对于不带权的图,一条路径长度是指该路径上的的边的条数;对于带权的图,一条路径的长度是指该路径上各个边权值的总和

简单路径和回路:若路径上各个顶点均不重复,则称这样的路径为简单路径。若路径上第一个顶点和最后一个顶点重合,则称这样的路径为回路或环。

子图:顶点和边都是原图的一部分。

连通图:在无向图中,如果图中任意一对顶点是连通的,则称为连通图

强连通图:在有向图中,若在每一个顶点vi和vj之间都存在一条从vi到vj的路径,也存在一条从vj到vi的路径,则称此图为强连通图。

生成树:一个连通图的最小连通子图称作该树的生成树,有n个顶点的连通图的生成树有n个顶点和n-1条边。

深度优先遍历(DFS):深度优先遍历借助栈结构,将可执行的节点元素逐个入栈,直到本条路径再也找不到可执行的节点。

广度优先遍历(BFS):广度优先遍历,又叫宽度优先搜索或横向优先搜索,是从根结点开始沿着树的宽度搜索遍历,将离根节点最近的节点先遍历出来,在继续深挖下去。

最小生成树:构成生成树这些边加起来权值是最小的,最小的成本让这个n个顶点连通。

深度优先遍历(DFS)

深度优先遍历借助栈结构,将可执行的节点元素逐个入栈,直到本条路径再也找不到可执行的节点。
代码如下:
在这里插入图片描述

		//递归
		void _DFS(size_t srci, 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);
			vector<bool> visited(_vertexs.size(), false);

			_DFS(srci, visited);
		}

广度优先遍历(BFS)

广度优先遍历,又叫宽度优先搜索或横向优先搜索,是从根结点开始沿着树的宽度搜索遍历,将离根节点最近的节点先遍历出来,在继续深挖下去。
在这里插入图片描述

代码如下:

void BFS(const V& src)
		{
			size_t srci = GetVertexIndex(src);

			// 队列和标记数组
			queue<int> q;
			vector<bool> visited(_vertexs.size(), false);
			
			q.push(srci);
			visited[srci] = true;
			int levelSize = 1;

			size_t n = _vertexs.size(); 
			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 < n; ++i)
					{
						if (_matrix[front][i] != MAX_W)//不是MAX_W就是相连的顶点
						{
							if (visited[i] == false)
							{
								q.push(i);//入队列
								visited[i] = true;//表示这个顶点访问过了
							}
						}
					}
				}
				cout << endl;
				levelSize = q.size();
			}
			cout << endl;
		}

kruskal(克鲁斯卡尔算法)

Kruskal算法是一种贪心算法,我们将图中的每个edge按照权值大小进行排序,每次从边集中取出权值最小且两个顶点都不在同一个集合的边加入生成树中!注意:如果这两个顶点都在同一集合内,说明已经通过其他边相连,因此如果将这个边添加到生成树中,那么就会形成环!这样反复做,直到所有的节点都连接成功。如何判断添加这条边会不会形成环,我们可以用到并查集。
特点:
1.只能使用图中权值最小的边来构成最小生成树
2.只能使用恰好n-1条边来连接图中的n个顶点
3.选用的n-1条边不能构成回路

代码如下:

		W Kruskal(Self& minTree)
		{
			size_t n = _vertexs.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);
			}

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

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

				if (!ufs.InSet(min._srci, min._dsti))
				{
					cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
					minTree._AddEdge(min._srci, min._dsti, min._w);
					ufs.Union(min._srci, min._dsti);
					++size;
					totalW += min._w;
				}
				else
				{
					cout << "构成环:";
					cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
				}
			}

			if (size == n - 1)
			{
				return totalW;
			}
			else
			{
				return W();
			}
		}

在这里插入图片描述

Prim(普里姆算法)

Prim算法是另一种贪心算法,和Kuskral算法的贪心策略不同,Kuskral算法主要对边进行操作,而Prim算法则是对节点进行操作,每次遍历添加一个点,这时候我们就不需要使用并查集了。

代码如下:


		W Prim(Self& minTree, const W& src)
		{
			size_t srci = GetVertexIndex(src);
			size_t n = _vertexs.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);
			}
			vector<bool> X(n, false);
			vector<bool> Y(n, true);
			X[srci] = true;
			Y[srci] = false;

			// 从X->Y集合中连接的边里面选出最小的边
			priority_queue<Edge, vector<Edge>, greater<Edge>> minq;
			// 先把srci连接的边添加到队列中
			for (size_t i = 0; i < n; ++i)
			{
				if (_matrix[srci][i] != MAX_W)
				{
					minq.push(Edge(srci, i, _matrix[srci][i]));
				}
			}

			cout << "Prim开始选边" << endl;
			size_t size = 0;
			W totalW = W();
			while (!minq.empty())
			{
				Edge min = minq.top();
				minq.pop();

				// 最小边的目标点也在X集合,则构成环
				if (X[min._dsti])
				{
					//cout << "构成环:";
					//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
				}
				else
				{
					minTree._AddEdge(min._srci, min._dsti, min._w);
					//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
					X[min._dsti]= true;
					Y[min._dsti] = false;
					++size;
					totalW += min._w;
					if (size == n - 1)
						break;

					for (size_t i = 0; i < n; ++i)
					{
						if (_matrix[min._dsti][i] != MAX_W && Y[i])
						{
							minq.push(Edge(min._dsti, i, _matrix[min._dsti][i]));
						}
					}
				}	
			}

			if (size == n - 1)
			{
				return totalW;
			}
			else
			{
				return W();
			}
		}

总结这两种算法:
构成最小生成树的方法:Kruskal算法和Prim算法。这两个算法都采用了逐步求解的贪心策略。Kruksal算法是对边进行操作,先取出边,然后判断边的两个节点,这样的话,如果一个图结构非常的稠密,那么Kruksal算法就比较慢了,而Prim算法只是对节点进行遍历,并使用visited进行标记,因此会相对于Kruksal算法,在稠密图方面好很多,因此Kruksal算法常用于稀疏图,而Prim算法常用于稠密图!

Dijkstra(迪杰斯特拉算法)

迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题,同时算法要求图中所以边的权重非负。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。

代码如下:

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] = 0;
			pPath[srci] = srci;

			// 已经确定最短路径的顶点集合
			vector<bool> S(n, false);

			for (size_t j = 0; j < n; ++j)
			{
				// 选最短路径顶点且不在S更新其他路径
				int u = 0;
				W min = MAX_W;
				for (size_t i = 0; i < n; ++i)
				{
					if (S[i] == false && dist[i] < min)
					{
						u = i;
						min = dist[i];
					}
				}

				S[u] = true;
				// 松弛更新u连接顶点v  srci->u + u->v <  srci->v  更新
				for (size_t v = 0; v < n; ++v)
				{
					if (S[v] == false && _matrix[u][v] != MAX_W
						&& dist[u] + _matrix[u][v] < dist[v])
					{
						dist[v] = dist[u] + _matrix[u][v];
						pPath[v] = u;
					}
				}
			}
		}
Bellman-ford(贝尔曼-福特算法)

美国应用数学家Richard Bellman (理查德.贝尔曼)于1958 年发表了该算法。此外Lester Ford在1956年也发表了该算法。因此这个算法叫做Bellman-Ford算法。其实EdwardF. Moore在1957年也发表了同样的算法,所以这个算法也称为Bellman-Ford-Moore算法。Bellman-ford 算法比dijkstra算法更具普遍性,因为它对边没有要求,可以处理负权边与负权回路的问题。缺点是时间复杂度过高,高达O(VE), V为顶点数,E为边数。

代码如下:

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

			// vector<W> dist,记录srci-其他顶点最短路径权值数组
			dist.resize(n, MAX_W);

			// vector<int> pPath 记录srci-其他顶点最短路径父顶点数组
			pPath.resize(n, -1);

			// 先更新srci->srci为缺省值
			dist[srci] = W();

			//cout << "更新边:i->j" << endl;


			// 总体最多更新n轮
			for (size_t k = 0; k < n; ++k)
			{
				// i->j 更新松弛
				bool update = false;
				cout << "更新第:" << k << "轮" << endl;
				for (size_t i = 0; i < n; ++i)
				{
					for (size_t j = 0; j < n; ++j)
					{
						// srci -> i + i ->j
						if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j])
						{
							update = true;
							cout << _vertexs[i] << "->" << _vertexs[j] << ":" << _matrix[i][j] << endl;
							dist[j] = dist[i] + _matrix[i][j];
							pPath[j] = i;
						}
					}
				}

				// 如果这个轮次中没有更新出更短路径,那么后续轮次就不需要再走了
				if (update == false)
				{
					break;
				}
			}


			// 还能更新就是带负权回路
			for (size_t i = 0; i < n; ++i)
			{
				for (size_t j = 0; j < n; ++j)
				{
					// srci -> i + i ->j
					if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j])
					{
						return false;
					}
				}
			}

			return true;
		}

flyod-warshall(佛洛伊德算法)

Floyd-Warshall算法是有Floyd于1962年提出,其可以计算有向图中任意两点之间的最短路径,此算法利用动态规划的思想将计算的时间复杂度降低为 。其核心思想是,最短路路径的本质就是比较在两个顶点之间中转点,比较经过与不经过中转点的距离哪个更短。类似Bellman-Ford算法,我们将此操作也称为松弛。

代码如下:

	void FloydWarshall(vector<vector<W>>& vvDist, vector<vector<int>>& vvpPath)
		{
			size_t n = _vertexs.size();
			vvDist.resize(n);
			vvpPath.resize(n);

			// 初始化权值和路径矩阵
			for (size_t i = 0; i < n; ++i)
			{
				vvDist[i].resize(n, MAX_W);
				vvpPath[i].resize(n, -1);
			}

			// 直接相连的边更新一下
			for (size_t i = 0; i < n; ++i)
			{
				for (size_t j = 0; j < n; ++j)
				{
					if (_matrix[i][j] != MAX_W)
					{
						vvDist[i][j] = _matrix[i][j];
						vvpPath[i][j] = i;
					}

					if (i == j)
					{
						vvDist[i][j] = W();
					}
				}
			}

			// abcdef  a {} f ||  b {} c
			// 最短路径的更新i-> {其他顶点} ->j
			for (size_t k = 0; k < n; ++k)
			{
				for (size_t i = 0; i < n; ++i)
				{
					for (size_t j = 0; j < n; ++j)
					{
						// k 作为的中间点尝试去更新i->j的路径
						if (vvDist[i][k] != MAX_W && vvDist[k][j] != MAX_W
							&& vvDist[i][k] + vvDist[k][j] < vvDist[i][j])
						{
							vvDist[i][j] = vvDist[i][k] + vvDist[k][j];

							// 找跟j相连的上一个邻接顶点
							// 如果k->j 直接相连,上一个点就k,vvpPath[k][j]存就是k
							// 如果k->j 没有直接相连,k->...->x->j,vvpPath[k][j]存就是x

							vvpPath[i][j] = vvpPath[k][j];
						}
					}
				}

				// 打印权值和路径矩阵观察数据
				for (size_t i = 0; i < n; ++i)
				{
					for (size_t j = 0; j < n; ++j)
					{
						if (vvDist[i][j] == MAX_W)
						{
							//cout << "*" << " ";
							printf("%3c", '*');
						}
						else
						{
							//cout << vvDist[i][j] << " ";
							printf("%3d", vvDist[i][j]);
						}
					}
					cout << endl;
				}
				cout << endl;

				for (size_t i = 0; i < n; ++i)
				{
					for (size_t j = 0; j < n; ++j)
					{
						//cout << vvParentPath[i][j] << " ";
						printf("%3d", vvpPath[i][j]);
					}
					cout << endl;
				}
			}
		}

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

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

相关文章

c语言练习(9周)

输入样例11输出样例7.0980 #include<stdio.h> int main() {int n, i;double s 1,a1;scanf("%d", &n);for (i 2; i < n; i) {a 1 / (1a);s a;}printf("%.4lf", s);return 0; } 题干输入10个整数&#xff0c;分别按输入正序、逆序显示。输…

工业数字化转型中的控制塔BI

工业数字化转型是当前工业领域的一个重要趋势&#xff0c;它通过应用先进的信息技术和数据分析方法&#xff0c;推动传统制造业向智能化、高效化、可持续发展的方向转变。在工业数字化转型中&#xff0c;控制塔BI&#xff08;Business Intelligence&#xff09;扮演着重要的角色…

【案例实战】NodeJS+Vue3+MySQL实现列表查询功能

这篇文章&#xff0c;给大家带来一个列表查询的功能&#xff0c;从前端到后端的一个综合案例实战。 采用vue3作为前端开发&#xff0c;nodejs作为后端开发。 首先我们先来看一下完成的页面效果。点击分页&#xff0c;可以切换到上一页、下一页。搜索框可以进行模糊查询。 后端…

什么是接口自动化测试?接口自动化测试的目的是什么?

1、什么是接口测试 接口测试是对系统或组件之间的接口的测试。主要用于检测外部系统与系统间以及内部各个子系统间的交互点。测试重点是检查数据交换、传递和控制管理过程&#xff0c;以及系统间的相互逻辑依赖关系等。 2、接口测试的目的 1> 尽早介入软件测试流程&#…

如何选择最适合 Android 的 SD 卡恢复软件?

所需要的只是心不在焉地点击了错误的按钮、行为不当的应用程序、或者软件或硬件故障。就这样&#xff0c;您的照片消失了&#xff0c;您的笔记无处可寻&#xff0c;您的文件也消失了。 如何选择最适合 Android 的 SD 卡恢复软件 对别人最好的可能对你不起作用&#xff0c;这取…

[NSSRound#6 Team]check(Revenge)

文章目录 考点tarfile文件覆盖漏洞&#xff08;CVE-2007-4559&#xff09;PIN码计算 解题过程非预期解预期解 考点 tarfile文件覆盖漏洞&#xff08;CVE-2007-4559&#xff09; Python 中 tarfile 模块中的extract、extractFile和extractall 函数中的目录遍历漏洞 允许 用户协…

kubernetes-控制器

目录 一、replicaset 二、deployment 1、版本迭代 2、回滚 3、滚动更新策略 4、暂停与恢复 三、daemonset 四、statefulset 五、job 六、cronjob 一、replicaset ReplicaSet用于保证指定数量的 Pod 副本一直运行 vim rs-example.ymlapiVersion: apps/v1 kind: Replic…

使用requests库进行HTTP爬虫编程

目录 一、安装requests库 二、发送HTTP请求 三、解析HTML页面 四、处理HTTP响应和异常 五、使用代理和会话管理 六、使用多线程或多进程提高效率 七、数据存储和处理 八、注意事项和总结 在当今的数字化世界中&#xff0c;数据已经成为了一种宝贵的资源。而网络爬虫程序…

在线开发平台是什么?有哪些优势?

目录 一、什么是在线开发平台&#xff1f; 二、企业为什么选择在线开发平台&#xff1f; &#xff08;1&#xff09;风险低&#xff0c;回报高 &#xff08;2&#xff09;可视化操作更形象 &#xff08;3&#xff09;易维护 三、在线开发平台功能展示 技术介绍 随着互联网和信息…

【ROS入门】雷达、摄像头及kinect信息仿真以及显示

文章结构 雷达信息仿真以及显示Gazebo仿真雷达配置雷达传感器信息xacro文件集成启动仿真环境 Rviz显示雷达数据 摄像头信息仿真以及显示Gazebo仿真摄像头新建xacro文件&#xff0c;配置摄像头传感器信息xacro文件集成启动仿真环境 Rviz显示摄像头数据 kinect信息仿真以及显示Ga…

第五章 I/O管理 九、磁盘的结构

目录 一、概念 二、磁盘的物理地址 1、定义&#xff1a; 2、图像&#xff1a; 如何读取一个“块”&#xff1a; 三、磁盘的分类 四、总结 一、概念 磁盘是由多个盘片和读写磁头组成的&#xff0c;每个盘片都有自己的读写磁头。盘片表面被划分成许多同心圆的磁道&#xff…

JS逆向爬虫---请求参数加密① 【某度翻译】

接口定位 抓包输入翻译关键词 全局搜索关键词,定位到接口https://fanyi.baidu.com/v2transapi 全局搜索sign 多次尝试定位变化参数sign 断点调试b函数 估值整个function&#xff0c;并测试函数运行结果 缺少r参数&#xff0c;可以通过多次输入调试&#xff0c;定位r参数的…

微服务初始和Nacos安装

一)初始微服务: 微服务是将一个大型的&#xff0c;单一的应用程序拆分成多个小型服务&#xff0c;每一个服务负责于特定的业务功能&#xff0c;并且可以通过网络来和其他服务进行通讯&#xff0c;是一个思想&#xff0c;将一个大的项目拆分成多个小的项目&#xff0c;多个小的项…

Android裁剪图片之后无法加载的问题

适配Android11之后更改了图片保存目录&#xff0c;导致裁剪之后图片一直无法加载&#xff08;fileNotfound&#xff09; 最主要的问题在于保存裁剪文件的目录不能为私有目录&#xff0c;因为裁剪工具是系统工具&#xff0c;无法直接访问项目本身的私有目录。 解决办法&#x…

【ChatGPT从瀑布模式到水母模式】如何赋能软件研发全流程?

【文末送书】今天推荐一本强大工具书《ChatGPT 驱动软件开发&#xff1a;AI 在软件研发全流程中的革新与实践》&#xff0c;本文将从其亮点与结构出发&#xff0c;详细阐发其对于运维、项目经理、程序员等的重要性与益处。 文章目录 导语内容作者简介专家推荐读者对象直播预告文…

apache seatunnel支持hive jdbc

上传hive jdbc包HiveJDBC42.jar到seatunel lib安装目录 原因是cloudera 实现了add batch方法 创建seatunnel任务文件mysql2hivejdbc.conf env {execution.parallelism = 2job.mode = "BATCH"checkpoint.interval = 10000 } source {Jdbc {url = "jdbc:mysql:/…

代购商城源码是否可以定制开发?

定制开发&#xff0c;符合个性需求 代购商城源码是现代电子商务中的重要工具&#xff0c;它为代购商提供了建立在线店铺、管理产品和订单、处理支付和物流等功能。然而&#xff0c;对于不同的代购商而言&#xff0c;在源码的基础上进行个性化定制开发无疑是提升竞争力和用户体验…

这个学习方式,用的太及时了!

学校思政学习是培养未来社会精英、提升学生政治觉悟的重要环节。在学生的成长过程中&#xff0c;思政学习扮演着至关重要的角色&#xff0c;不仅有助于提高学生的政治素质&#xff0c;还能够培养他们的思维能力、价值观念&#xff0c;使他们更好地为社会和国家的发展贡献力量。…

[架构之路-248/创业之路-79]:目标系统 - 纵向分层 - 企业信息化的呈现形态:常见企业信息化软件系统 - 供应链管理

目录 前言&#xff1a; 一、企业信息化的结果&#xff1a;常见企业信息化软件 1.1 供应链管理 1.1 什么是供应链与供应链管理What 1.2 为什么需要供应链管理系统Why&#xff1f; 1.3 谁需要供应链管理系统who&#xff1f; 1.4 供应链管理在企业管理中的位置where 1.5 什…

漆料店信息展示服务预约小程序的作用是什么

漆料在工程、家庭装修等场景中都是不可缺的&#xff0c;而在种类/品牌方面更是众多&#xff0c;无论厂家直营店还是经销商&#xff0c;市场中都有很多&#xff0c;在生意方面&#xff0c;尤其是较大的店面&#xff0c;除了本地生意&#xff0c;外地客户也有一定拓展。 但由于种…