《数据结构》王道 第六章 图

这篇具有很好参考价值的文章主要介绍了《数据结构》王道 第六章 图。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 图的定义和基本术语

1.1 图的定义

《数据结构》王道 第六章 图

1.2 无向图和有向图

《数据结构》王道 第六章 图

1.3 简单图和多重图

《数据结构》王道 第六章 图

1.4 顶点的度、入度、出度

《数据结构》王道 第六章 图

1.5 顶点-顶点的关系描述

《数据结构》王道 第六章 图

1.6 连通图和强连通图

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

1.7 子图、生成子图

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

1.8 连通分量(无向图)

《数据结构》王道 第六章 图

1.9 强连通分量(有向图)

《数据结构》王道 第六章 图

1.10 生成树、生成森林

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

1.11 边的权、带权图/网

《数据结构》王道 第六章 图

1.12 无向完全图、有向完全图、稀疏图、稠密图

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

2. 图的存储

2.1 邻接矩阵法

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

2.1.1 邻接矩阵存储带权图(网)

《数据结构》王道 第六章 图

2.1.2 邻接矩阵的性能分析

《数据结构》王道 第六章 图

2.1.3 邻接矩阵的性质

《数据结构》王道 第六章 图
以此类推,可以得到A2 的矩阵。
《数据结构》王道 第六章 图
A3 也是同样的道理,则表示A[i][j] 由 i 到 j 路径长度为3的路径数目。
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

2.2 邻接表法(顺序+链式存储)

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

这种存储图的方法其实跟树的孩子表示法有点相似。
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
邻接矩阵存储无向图时,一条边会有两个顶点都记录着,所以边结点的数量是边的两倍,即2 * |E|。算各个结点的度也比较容易,直接看各个结点的指针区域没有连着几个结点。
当存储的是有向图时,边结点的数量就是边数,即|E|,出度就是对应结点指针区域后面连着的结点数量,而入度就得把整个邻接表遍历一遍才能知道。

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

2.3 十字链表(存储有向图)

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
十字链表找某个结点所有的边(出边和入边)都是很方便的。
《数据结构》王道 第六章 图
不会考代码。

2.4 邻接多重表(无向图)

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

3. 图的基本操作

《数据结构》王道 第六章 图

3.1 判断图中是否存在某条边

《数据结构》王道 第六章 图
有向图类似:
《数据结构》王道 第六章 图

3.2 列出与某个顶点邻接的边

《数据结构》王道 第六章 图
因为邻接矩阵的一行或一列有V个元素,所以以上邻接矩阵的操作的时间复杂度是O(|V|)。
《数据结构》王道 第六章 图

3.3 插入顶点

《数据结构》王道 第六章 图

3.4 删除顶点

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

3.5 添加边

《数据结构》王道 第六章 图

3.6 求第一个邻接点(常用到)

考试可以直接调用这个接口。
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

3.7 找下一个邻接点(常用到)

考试可以直接调用这个接口。
《数据结构》王道 第六章 图

3.8 获取对应边的权值或设置权值

《数据结构》王道 第六章 图

4. 图的遍历

4.1 广度优先遍历(BFS)

图的广度优先遍历有点类似于树的广度优先遍历(层序遍历)。
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

4.1.1 代码实现

《数据结构》王道 第六章 图

4.1.2 广度优先遍历序列

《数据结构》王道 第六章 图

4.1.3 遍历序列的可变性

《数据结构》王道 第六章 图

4.1.4 算法存在的问题

《数据结构》王道 第六章 图

4.1.5 BFS算法(最终版)

《数据结构》王道 第六章 图

4.1.6 复杂度分析

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

4.1.7 广度优先生成树

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

4.1.8 广度优先生成森林

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

4.2 深度优先遍历(DFS)

《数据结构》王道 第六章 图

4.2.1 代码实现

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

4.2.2 算法实现的问题

《数据结构》王道 第六章 图

4.2.3 DFS算法(最终版)

《数据结构》王道 第六章 图

4.2.4 复杂度分析

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

4.2.5 遍历序列的可变性

《数据结构》王道 第六章 图

4.2.6 深度优先生成树

《数据结构》王道 第六章 图

4.2.7 图的遍历和图的连通性

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

5. 最小生成树

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

5.1 概念

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

5.2 Prim算法(普里姆)

《数据结构》王道 第六章 图
从P城这个顶点开始构建生成树:
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
整个过程就是上面这样子,当然按照这个算法,一个图从一个顶点去生成树也可能有多个最小生成树。《数据结构》王道 第六章 图
例如,也可以是这样,最小代价是一样的,就是树不同而已。
从“农场”顶点开始构建生成树:
《数据结构》王道 第六章 图
最小代价还是一样。

5.2.1 实现思想

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

5.3 Kruskal算法(克鲁斯卡尔)

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

5.3.1 实现思想

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

6. 最短路径

《数据结构》王道 第六章 图

6.1 BFS求无权图的单源最短路径

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
举个例子,以顶点2作为起点:
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

6.2 Dijkstra算法(迪杰斯特拉)

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
Dijkstra算法有向图和无向图都可以用。
《数据结构》王道 第六章 图
这样我们研究有向图:
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

6.2.1 时间复杂度

《数据结构》王道 第六章 图
循环遍历dist数组,找出最小值,所需时间复杂度是O(n);检查所有邻接自Vi ,如果是用邻接矩阵存储图的话,则需要扫描Vi 对应的一整行,即O(n),所以总的复杂度是O((n+n)*(n-1)),即O(n2 )。如果是用邻接表存储图的话,Vi 对应的链表最多有n-1个元素,所以总的时间复杂度是O(((n-1)+n) * (n-1)),同样是O(n2 )。

《数据结构》王道 第六章 图
Prim算法实现思想跟Dijkstra算法实现的思想是很类似的。只不过Prim算法的lowCost数组是指,其他没有加入树的顶点要加入到树的代价;而Dijkstra算法的dist数组是指当前顶点到其他顶点的最短路径。而它们的时间复杂度是一样的。

6.2.2 Dijkstra算法不适用于带负值的带权图

《数据结构》王道 第六章 图
如果这个图采用Dijkstra算法,v0到v2的最短路径是7。
《数据结构》王道 第六章 图

6.3 Floyd算法

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

6.3.1 核心代码和复杂度

《数据结构》王道 第六章 图
因为有三层循环,每个for循环都是n,所有时间复杂度是O(n3 ),即O(|V|3 )。最外一层循环是用来考虑是否采用Vk 作为中转点的。
而这个算法需要两个二维数组A和path,所有空间复杂度是O(2*n2 ),即O(|V|2 )。

举个例子:
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

6.3.2 可用于负权值带权图

《数据结构》王道 第六章 图

6.3.3 不能解决的问题

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

7. 有向无环图

7.1 描述表达式

《数据结构》王道 第六章 图
树是自顶向下的,所以树可以算作一种有向无环图,就是把上面的指针指向同个结点也还是有向无环图。
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
相同的子树可以合并,从而减少结点数量,节省空间。
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
所以最后形成的有向无环图是这样子的:
《数据结构》王道 第六章 图
曾经真题也出现过这样的题:
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

7.1.1 总结规律

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
再往上层已经没有可以合并的了,所以最后的有向无环图就是以上所示。

7.2 拓扑排序

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
有两个选择,我们先选择“准备厨具”:
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
到这里之后,就依次执行下去,我们可以总结出一个规律:
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
执行到这里时,已经没办法继续执行下去了。

7.2.1 核心代码

《数据结构》王道 第六章 图
拓扑排序,我们先处理的是入度为0的顶点。
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

7.2.2 用DFS实现拓扑排序

对于有向无环图G中的任意结点u、v,它们之间的关系必然是一下三种之一:

  1. 假设结点u是结点v的祖先,则在调用DFS访问u的过程中,必然会在这个过程结束之前递归地对 v 调用DFS访问,即v的DFS函数结束时间先于u的DFS结束时间。从而可以考虑在DFS调用过程中设定一个时间标记,在DFS调用结束时,对各结点计时。因此,祖先的结束时间必然大于子孙的结束时间。

  2. 若u是结点v的子孙,则v为u的祖先,按上述思路,v 的结束时间大于u的结束时间。

  3. 若u和v没有关系,则u和v在拓扑序列的关系任意。

从而按结束时间从大到小,可以得到一个拓扑序列。

下面给出利用DFS求各结点结束时间的代码。至于拓扑序列,将结束时间从大到小排序即可得到(实际上和深度优先遍历算法完全相同,只不过加入了time变量)。

bool visited[MAX_VERTEX_NUM];    //访问标记数组
void DFSTraverse(Graph G){
	for(v=0;v<G.vexnum;++v){
		visited[v]=false;        //初始化访问标记数组 
	}
	time=0;
	for(v=0;v<G.vexnum;++v){
		if(!visited[v]){
			DFS(G,v);
		}
	}
} 
void DFS(Graph G,int v){
	visited[v]=true;
	visit(v);
	for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
		if(!visited[w]){         //w为v的尚未访问的邻接顶点 
			DFS(G,w); 
		}
	}
	time=time+1;
	finishTime[v]=time;
}

7.3 逆拓扑排序

《数据结构》王道 第六章 图
拓扑排序是先处理入度为0的顶点,而逆拓扑排序是先处理出度为0的结点。
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
这里也有多种选择,所以形成的逆拓扑排序序列也可以有多个。
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

7.3.1 核心代码

//这里采用的是邻接矩阵法
bool ni-TopologicalSort(Graph G){
	InitStack(S);        //初始化栈,存储出度为0的顶点,这里是假设已经初始化好outdegree数组(记录当前顶点的出度)和print数组的 
	for(int i=0;i<G.vexnum;i++){
		if(outdegree[i]==0)
			Push(S,i);   //将所有出度为0的顶点进栈 
	} 
	int count=0;         //记录当前已经输出的顶点数
	while(!IsEmpty(S)){  //栈不空则存在出度为0的顶点 
		Pop(S,i);        //栈顶元素出栈
		print[count++]=i;//将输出顶点保存在print数组中
		for(int j=0;j<G.vexnum;j++){     //这里我采用的是邻接矩阵的存储方式 
			//将所有指向i的顶点的出度减1,并且将出度减为0的顶点压入栈S 
			if(A[j][i]==1){              //说明j->i有出边 
				if(!(--outdegree[j])){
					Push(S,j);           //出度为0,则入栈 
				}
			}
		} 
	} 
	if(count<G.vexnum){    //count小于顶点数 
		return false;      //排序失败,有向图中有回路 
	}else{
		return true;       //逆拓扑排序成功 
	} 
}

《数据结构》王道 第六章 图

7.3.2 用DFS实现逆拓扑排序

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
当出现回路时,可以参考这个博主的链接:
图的逆拓扑排序
《数据结构》王道 第六章 图

7.4 关键路径

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

7.4.1 求关键路径的步骤

《数据结构》王道 第六章 图

求所有路径的最早发生时间

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

求所有事件的最迟发生时间

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图

求所有活动的最早发生时间

《数据结构》王道 第六章 图

求所有活动的最迟发生时间

《数据结构》王道 第六章 图

求所有事件的时间余量

《数据结构》王道 第六章 图

求得关键活动和关键路径

《数据结构》王道 第六章 图

7.4.2 关键活动、关键路径的特征

《数据结构》王道 第六章 图
《数据结构》王道 第六章 图
《数据结构》王道 第六章 图文章来源地址https://www.toymoban.com/news/detail-428031.html

到了这里,关于《数据结构》王道 第六章 图的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构 第六章 图——图的遍历

    在前面我们知道,树是一种非线性结构,为了方便它在计算机中的存储,对树进行遍历使它线性化。 而图同样也是一种非线性结构,但是图又是一种不同于树的多对多结构,所以在前面我们将其转换为了多个一对多的结构来描述它的存储结构。 图的遍历同树类似,也是从某

    2024年02月08日
    浏览(45)
  • 数据结构与算法分析 第六章 图 作业讲解

     参考教材: 《数据结构(C语言版 第2版)》 严蔚敏,李冬梅,吴伟民编著,人民邮电出版社,2022年版。 截图未标明出处均为原创或取自《数据结构(C语言版 第2版)》~   本文对应的作业题讲解视频:   数据结构与算法分析作业讲解视频合集 https://www.bilibili.com/video/BV1N

    2024年02月03日
    浏览(47)
  • 王道_数据结构 1.1_1数据结构的基本概念&1.1_2数据结构的三要素

    本节主要介绍数据结构的基本概念与三要素 笔记来源: B站 王道 数据结构 数据是 信息的载体 ,是描述客观事物属性的数、字符串所有能输入到计算机中并 被计算机程序识别和处理 的符号的集合。 1、数据元素、数据项概念 数据元素 :是数据的基本单位, 通常作为一个整

    2024年02月22日
    浏览(31)
  • 数据结构(王道)——数据结构之 树

           树的概念补充: 结点之间的关系描述    结点、树的属性描述: 有序树、无序树: 1、第i层至多有m^(i-1)个结点 2、高度为h的m叉树至多有(m^h-1)/(m-1)个结点   3、高度为h的m叉树至少有h个结点 高度为h,度为m的树至少有h+m-1个结点   4、具有n个结点的m叉树的最小高度

    2024年02月17日
    浏览(54)
  • 【数据结构】【王道】【数据结构实现】文章目录

    持续更新中。。。 数据结构 链接 顺序表实现及基本操作(可直接运行) 文章链接 无头结点单链表的实现及基本操作(可直接运行) 文章链接 带头结点单链表的实现及基本操作(可直接运行) 文章链接 双链表的实现及基本操作(可直接运行) 文章链接 循环链表的实现及

    2023年04月08日
    浏览(92)
  • 【王道考研】王道数据结构与算法详细笔记(全)

    目录 第一章 数据结构绪论  1.1 数据结构的基本概念 1.2 数据结构的三要素 1.2.1. 数据的逻辑结构 1.2.2. 数据的存储结构(物理结构) 1.2.3. 数据的运算 1.2.4. 数据类型和抽线数据类型 1.3 算法的基本概念 1.4 算法的时间复杂度 1.5 算法的空间复杂度 第二章 线性表 2.1 线性表的定

    2024年02月08日
    浏览(53)
  • 数据结构学习笔记(王道)

    PS:本文章部分内容参考自王道考研数据结构笔记 1.1. 数据结构 数据:是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素:数据的基本单位,一个数据元素可由若干数据项组成。 数据项:数据的不可分割的最

    2024年02月03日
    浏览(261)
  • 王道考研数据结构——链表

    找到头节点就相当于找到了整个链表 Linklist Lnode*是一个东西 大部分使用的带头结点,比较方便!带头结点只维护指针域,不维护数据域 找前驱节点+插入节点(可以单独封装成一个函数)  如果不带头节点的话,那么插入和删除头节点的话都需要特殊处理,即重新修改头指针的

    2024年02月16日
    浏览(60)
  • 【2023王道数据结构】王道数据结构课后代码题汇总答案C、C++代码实现完整版大全(可直接运行)

    本文章为 2023王道数据结构专栏 导航贴,正在积极更新中! 本专栏文章将王道一些 课后算法设计题目 的全部实现(答案解析全部都是伪码或者函数的部分实现,不可调试运行), 同时包含各个章节的经典算法数据结构的实现以及一些经典的算法 本专栏使用人群:复习数据

    2024年02月16日
    浏览(41)
  • 王道数据结构精选习题及解析

    暴力法的时间复杂度为O(n²) 不要忽略有序性 思路:因为是有序的顺序表,所以重复的元素一定是连在一起的。那我们就使用两个指针,一个指针指向当前不重复有序表的最后一个元素,另一个会从头到尾遍历整个有序表,称为工作指针。 我们让工作指针往后移,如果与当

    2024年02月10日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包