数据结构——图论详细笔记

一 图论基本概念

 

 

 

Directed Acyclic Graph (DAG)

 

二 图的存储

 ①邻接矩阵(适用于稠密图)

 ②邻接表(适用于稀疏图)

 

三、图的遍历 

①深度优先搜索


//(基于邻接表实现,以有向图为例)
//DFS:Depth First Search 深度优先搜索
//1、访问起始顶点  2、访问一个未访问过的邻接顶点 3、若所有邻接顶点都已被访问,则回溯 4、所有顶点都被访问,遍历结束
void dfs(int start, bool visited[])
{
	//访问起始结点
	cout << verList[start].ver << '\t';
	visited[start] = true;
	//找到顶点表中该顶点对应的链表
	edgeNode* node = verList[start].head;
	while (node)
	{
		if (!visited[node]) dfs(visited[node],visited); //访问未访问过的邻接结点
	    node = node->next; //跳过已访问的结点
	}
	//当所有邻接结点都已被访问,则回溯
}  //递归函数结束时,生成一棵深度优先搜索树
 
void dfs()
{
   //访问标志数组初始化
	bool* visited=new bool[Vers];  //Vers:顶点数量
	for (int i = 0; i < Vers; i++)
		Vers[i] = false;
	for (int i = 0; i < Vers; i++)
	{
		if (visited[i] == true) continue; //寻找下一个树遍历的起始结点
		dfs(i, visited);
	} //生成深度优先搜索森林(起点选择不同,生成结果不同,有些情况能只生成一棵树)
}

DFS将所有边和顶点遍历一次,若采用邻接数组,时间复杂度为O(V²),若采用邻接矩阵,时间复杂度为O(V+E)。

②广度优先搜索


//BFS:Breadth First Search 广度优先搜索
//1、访问起始顶点 2、依次访问起始顶点的所有未访问的邻接结点  3、所有顶点都被访问,遍历结束
void bfs()
{
	queue<int>  q;
	bool* visited = new bool[Vers];
	for (int i = 0; i < Vers; i++)
		visited[i] = false;
	for (int i = 0; i < Vers; i++)
	{
		if (visited[Vers] == true)  continue;  ///寻找一棵新的搜索树的起始结点
		q.push(i);  //结点入队,开始一棵搜索树的生成
		while (!q.empty())
		{
			int currentNode = q.front();
			q.pop();
			if (visited[currentNode])  continue; //这里需要注意,比如1的邻接结点2、3入队,而3邻接于2,在访问3的过程中已访问了2,所以2出队时无需再次访问
			cout << verList[currentNode].ver << '\t'; //访问当前结点
			visited[currentNode] = true;
			//找到顶点表中该顶点对应的链表
			edgeNode* node = verList[currentNode].head;
			//将未访问的邻接顶点入队
			while (node)
			{
				if (!visited[node->end]) q.push(node->end); //将未访问的邻接顶点入队
				node = node->next;
			}  
		}
	}
}

 

可用优先级队列实现。

BFS将所有边和顶点遍历一次,若采用邻接数组,时间复杂度为O(V²),若采用邻接矩阵,时间复杂度为O(V+E)。 

四、图的应用

1、欧拉路径(一笔画问题) 

欧拉路径:在图中找到一条路径经过每一条边,且每条边只经过一次

欧拉回路:起点和终点相同的欧拉路径

2、图的连通性

①无向图的连通性

②有向图的连通性(Kosaraju算法)

G图和Gr图分别进行一次dfs,时间复杂度为O(V+E)

3、拓扑排序

能进行拓扑排序的图是有向无环图(DAG),顶点表示活动的图称为AOV网((activity on the vertex)

 

 

4、关键路径

AOE(activity on the edge)网是另一种有向无环图,有向边的权值表示活动的持续时间,弧尾表示活动的起点,弧头表示活动的终点,边的方向表示事件发生的先后顺序。可以用AOE网表示一项工程,如下图A为工程的源点,G为工程的收点。关键路径具有从源点到收点的最长路径长度,其上的活动称为关键活动。

顶点x的最早发生时间为ee(x),最晚发生时间为le(x),定义le(x)-ee(x)=△e(x)为时间余量,满足△e(x)=0的顶点x为关键活动,找到所有时间余量为0的顶点即找到了关键路径。

 算法实现:

①进行拓扑排序

②按照拓扑序列,正向遍历每一个顶点x,计算最早发生时间ee(x):

所有顶点的ee初始化为0,假设边<u,v>的长度为Luv,对于每一个顶点u,检查其后继顶点v,若ee(u)+Luv>ee(v),更新ee(v)=ee(u)+Luv 。ee(G)即为工程的最短完成时间,即关键路径的长度Len.

③按照拓扑序列,逆向遍历每一个顶点x,计算最晚发生时间le(x):

所有顶点的le初始化为Len,假设边<u,v>的长度为Luv,对于每一个顶点u,检查其后继顶点v,若le(v)-Luv<le(u),更新le(u)=le(v)-Luv 。

④计算△e(x)=le(x)-ee(x),输出△e(x)=0的顶点即为关键活动,构成一条关键路径。

5、最小生成树

最小生成树:边的权值之和最小的生成树

①Kruskal算法

[选择边][优先级队列+并查集]

 

 

②Prim算法

[选择点]

 

最小生成树不一定唯一,当所有边的权值不同时,最小生成树唯一。 

6、最短路径

单源最短路径:计算从一个顶点出发,到其他每一个顶点的最短路径。算法实现的目标是得到一个顶点出发到其他顶点的最短路径,并获取路径的结构。

①非加权单源最短路径(BFS)

 

 

distance[i]:源点到顶点i的最短路径

prev[i]:最短路径中i的前驱顶点

用bfs实现(利用队列),输出使用递归 

 

时间复杂度:O(V+E) 

②加权单源最短路径(Dijkstra算法)

 

 

 

 

Dijkstra算法,只适用于所有路线的权值都为正的,如果有负权值路线则算法失效,因为第一个点就不能确保是最短路径(可能存在权值总和为负数的回路)。 

③带负权值单源最短路径(SPFA)

SPFA适用于无负环图

 

 

当图中无环时可以按照拓扑排序的序列改进Dijkstra算法,使时间复杂度达到线性,算法实现类似SPFA的过程。

总结一下,Dijkstra的一般性算法适用于无负权图,时间复杂度为O(V²),使用优先级队列可以是复杂度降低到O((V+E)logV),当图无环时,采用拓扑排序+队列可以使时间复杂度降低到线性。当存在负权时,Dijkstra算法可能出错,可以采用SPFA算法,时间复杂度为O(VE)。

 ④所有顶点对之间的最短路径(Floyd算法)

①想要找到所有顶点对之间的最短路径,可以使用V次Dijkstra算法,时间复杂度达到O(V^3)或者O(V^2logV);

②第二种经典解决算法是Floyd算法,使用穷举的思想,不断更新结点对之间的最短距离。

 

 

 

 

完结撒花!!! 

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

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

相关文章

STM32学习和实践笔记(33):待机唤醒实验

1.STM32待机模式介绍 很多单片机具有低功耗模式&#xff0c;比如MSP430、STM8L等&#xff0c;我们的STM32也不例外。默认情况下&#xff0c;系统复位或上电复位后&#xff0c;微控制器进入运行模式。在运行模式下&#xff0c;HCLK 为CPU提供时钟&#xff0c;并执行程序代码。这…

【GPU原理】1.线程和缓存的关系

一、GPU如何做并行计算 1.简单的串行计算 对于如上的运算AXY&#xff0c;每次运算我们需要从内存读取两个数据&#xff0c;一个是x[i]&#xff0c;一个是y[i]&#xff0c;最后存回y[i]。这里面有一个FMA的操作&#xff08;融合乘加&#xff08;FMA&#xff09;指令是RISC处理器…

基于Qt GraphicView 解析 CIM/G 电力接线图文件

本文讲述了如何使用Qt的框架来渲染展示标准的CIM/G格式的图形文件&#xff0c;也就是公用信息模型&#xff08;common information model&#xff0c;CIM&#xff09;中的G文件部分的内容。这是一种电力系统图形的交换规则&#xff0c;用于电网图形交换。 [by amjieker] CIM/G …

Ai晚班车531

1.中央网信办等三部门&#xff1a;加快推进大模型、生成式人工智能标准研制。 2.中国石油与中国移动、华为、科大讯飞签署合作协议。 3.Opera浏览器与谷歌云合作&#xff0c;接入 Gemini 大模型。 4.谷歌 Gemini 加持Chromebook Plus。 5.英飞凌&#xff1a;开发 8kW和12kW…

《技术人求职之道》:从入职到离职,全方位解析求职艺术

一、引言二、内容&#xff1a;该求职专栏包含什么三、结果&#xff1a;通过该专栏你将收获什么四、说明&#xff1a;关于该专栏的一些问题解答五、后记 一、引言 求职&#xff0c;这是每个人职业生涯中必经的阶段&#xff0c;技术人亦不例外。上一个冬天的寒风已过&#xff0c…

获取 Bean 对象更加简单的方式

获取 bean 对象也叫做对象装配&#xff0c;是把对象取出来放到某个类中&#xff0c;有时候也叫对象注⼊。 对象装配&#xff08;对象注⼊&#xff09;即DI 实现依赖注入的方式有 3 种&#xff1a; 1. 属性注⼊ 2. 构造⽅法注⼊ 3. Setter 注⼊ 属性注入 属性注⼊是使⽤ Auto…

MySQL性能分析工具——EXPLAIN

性能分析工具——EXPLAIN 1、概述 定位了查询慢的SQL之后&#xff0c;我们就可以使用EXPLAIN或DESCRIBE工具做针对性的分析查询语句 。 DESCRIBE语句的使用方法与EXPLAIN语句是一样的&#xff0c;并且分析结果也是一样的。 MySQL中有专门负责优化SELECT语句的优化器模块&…

报表工具DataEase技术方案(二)

一、DataEase报表功能开发流程 1. 创建数据源 2. 创建数据集 可以创建多种来源的数据集&#xff0c;这里以SQL数据集为例。 数据集SQL中可以添加参数&#xff0c;仪表板展示数据时可以根据参数来筛选数据。 数据集添加计算字段 3. 创建仪表板 &#xff08;1&#xff09;组合…

关于Posix标准接口和Nuttx操作系统

基本介绍 主要参考&#xff1a; Linux 系统中的 POSIX 接口详细介绍_linux posix-CSDN博客 POSIX&#xff08;Portable Operating System Interface&#xff0c;可移植操作系统接口&#xff09;是由 IEEE&#xff08;Institute of Electrical and Electronics Engineers&#x…

LLVM入门教学——SanitizerCoverage插桩(Linux)

1、介绍 LLVM 的 SanitizerCoverage 是一种代码覆盖工具&#xff0c;设计用于支持基于 fuzzing 的测试和其他安全相关工具。SanitizerCoverage 在编译时插桩代码&#xff0c;以在运行时收集覆盖信息&#xff0c;从而帮助识别未覆盖的代码路径&#xff0c;提高测试的有效性和全…

详细介绍运算符重载函数,清晰明了

祝各位六一快乐~ 前言 1.为什么要进行运算符重载&#xff1f; C中预定义的运算符的操作对象只能是基本数据类型。但实际上&#xff0c;对于许多用户自定义类型&#xff08;例如类&#xff09;&#xff0c;也需要类似的运算操作。这时就必须在C中重新定义这些运算符&#xff…

摄影后期照片编辑工具:LrC2024 for Mac/win 中文激活版

LrC2024&#xff08;Lightroom Classic 2024&#xff09;是 Adobe 公司推出的一款专业级别的照片编辑和管理软件。它是 Lightroom Classic CC 的升级版&#xff0c;具有更多的功能和改进。 这款软件主要用于数字摄影师和摄影爱好者处理、编辑和管理他们的照片。它提供了一套强大…

锅炉智能制造工厂工业物联数字孪生平台,推进制造业数字化转型

在制造业快速发展的今天&#xff0c;数字化转型已经成为企业提升竞争力的关键途径。锅炉智能制造工厂工业物联数字孪生平台&#xff0c;作为一种创新的技术解决方案&#xff0c;正以其独特的优势&#xff0c;为制造业的数字化转型提供强大动力。锅炉智能制造工厂工业物联数字孪…

【网络研究观】-20240531

战争揭开美国武器优势的面纱 随着俄军在哈尔科夫地区稳步推进&#xff0c;乌克兰战争对美国国防机器而言是一场灾难&#xff0c;这一点越来越明显&#xff0c;这不仅是因为我们的援助未能挽救乌克兰的撤退和可能的失败。更重要的是&#xff0c;这场战争无情地暴露了我们国防体…

我用大模型校稿出书的经验心得

1. 第一本AI校稿的书 我的新书《云计算行业进阶指南》已经出版&#xff0c;本书使用了大模型进行AI校对书稿。 在本文稿发布前&#xff0c;我问了好几个AI&#xff0c;AI都说“还没有出版书籍宣称自己使用了AI校稿”&#xff0c;因此我可以说&#xff1a; 本书是第一本公开宣称…

Docker搭建Redis主从 + Redis哨兵模式(一主一从俩哨兵)

我这里是搭建一主一从&#xff0c;俩哨兵&#xff0c;准备两台服务器&#xff0c;分别安装docker 我这里有两台centos服务器 主服务器IP&#xff1a;192.168.252.134 从服务器IP&#xff1a;192.168.252.135 1.两台服务器分别拉取redis镜像 docker pull redis 2.查看镜像 d…

编写备份MySQL 脚本

目录 环境准备 增量备份 增量备份和差异备份 完整代码如下 测试脚本是否正常 星期天运行脚本&#xff08;完全备份&#xff09; 星期一运备份脚本&#xff08;增量备份&#xff09; 星期二备份数据&#xff08;其他天--增量备份&#xff09; 星期三备份数据&#xff08;差异备…

cobalt strike基础测试

下载链接4.3&#xff1a;https://pan.baidu.com/s/1E_0t30tFWRiE5aJ7F-ZDPg 链接4.0&#xff1a;https://pan.baidu.com/s/1SkMmDem3l6bePqIDgUz2mA 提取码&#xff1a;burp 一、简介&#xff1a; cobalt strike(简称CS)是一款团队作战渗透测试神器&#xff0c;分为客户端…

C++笔试强训day37

目录 1.旋转字符串 2.合并k个已排序的链表 3.滑雪 1.旋转字符串 链接https://www.nowcoder.com/practice/80b6bb8797644c83bc50ac761b72981c?tpId196&tqId37172&ru/exam/oj 如果 A 字符串能够旋转之后得到 B 字符串的话&#xff0c;在 A 字符串倍增之后的新串中&am…

linux驱动学习(二)之点灯

需要板子一起学习的可以这里购买&#xff08;含资料&#xff09;&#xff1a;点击跳转 如何实现对硬件控制 分析硬件原理图&#xff08;开发板的原理图&#xff09;----> 分析硬件的控制方法 ---> 控制硬件时&#xff0c;所要用到的寄存器 ----> 了解控制硬件寄存器的…