假设图G采用邻接表存储

上传人:xmg****18 文档编号:117141937 上传时间:2019-11-18 格式:PPT 页数:106 大小:2.16MB
返回 下载 相关 举报
假设图G采用邻接表存储_第1页
第1页 / 共106页
假设图G采用邻接表存储_第2页
第2页 / 共106页
假设图G采用邻接表存储_第3页
第3页 / 共106页
假设图G采用邻接表存储_第4页
第4页 / 共106页
假设图G采用邻接表存储_第5页
第5页 / 共106页
点击查看更多>>
资源描述

《假设图G采用邻接表存储》由会员分享,可在线阅读,更多相关《假设图G采用邻接表存储(106页珍藏版)》请在金锄头文库上搜索。

1、第七章 图 第7章 图 一、教学内容: 1、图的基本概念 2、图的存储结构(邻接矩阵、邻接表); 3、图的遍历(深度优先搜索、广度优先搜索); 4、最小生成树(kruskul算法、prim算法); 5、最短路径(dijkstra算法、floyd算法); 6、AOV网络与拓扑排序; 7、AOE网络与关键路径。 第7章 图 二、教学要求: 1、理解图的基本概念,熟悉图的各种存储结构及其构 造算法; 2、熟练掌握图的两种搜索路径的遍历; 3、掌握构造最小生成树的方法,并理解算法; 4、掌握用Dijkstra方法求解单源最短路径问题,理解 Floyd(弗洛伊德)算法思想; 5、掌握求活动网络的拓扑排序

2、的方法,并理解算法; 6、掌握求解关键路径的方法。 第7章 图 教学重点: 图的定义、术语及其含义,各种图的邻接矩阵 表示法及其类型说明,图的按深度优先搜索遍 历方法和按广度优先搜索遍历方法,生成树和 最小生成树的概念, Prim 算法,拓扑序列和 拓扑排序的概念和算法思想,关键路径的算法 思想,最短路径的算法思想。 教学难点: 图的存储表示、关键路径,最短路径算法 。 引言 图(Graph)是一种较线性表和树更为复杂 的数据结构。 图形结构中,结点之间 的关系可以是任意的 ,任意两个数据元素之间都可能相关。 应用广泛: 如电路网络分析、交通运输、管理与线路的铺 设、印刷电路板与集成电路的布线

3、等众多直接与 图有关的问题,它们必须用图的有关方法进行处 理; 另外像工作的分配、工程进度的安排、课程表 的制订、关系数据库的设计等许多实际问题,如 果间接地用图来表示,处理起来比较方便。 问题的提出 假设有”平顶山”、”郑州”、”洛阳”、”许昌”、”漯河”五 城市的交通图如下,完成如下要求: 1:对任意输入的两个城市,输出它们之间的直接距 离,有则输出实际距离,无则输出道路不直接相通。 2:对任意一个城市,输出都能够直接通达哪些城市 ,距离多少? 5 1 3 24 平顶山 郑州 洛阳 许昌 漯河 100 150 120 150 200 180 第7章 图 7.1 图的定义和术语 7.2 图的

4、存储结构 7.3 图的遍历操作 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径 7.1 图的定义和术语 1、图的结构定义、图形结构特点 2、顶点、弧、边、弧头、弧尾 3、无向图和有向图 4、完全图和有向完全图 5、网、子图 6、顶点的度、入度和出度、 边、弧与各顶点度的关系 7.1 图的定义和术语 7、路径、路径长度、回路(环)、简单路 径 8、连通、连通图、连通分量 9、强连通图、强连通分量 10、生成树、有向树、生成森林 7.2 图的存储表示 n图的数组(邻接矩阵)存储表示(重点) n图的邻接表存储表示(重点) n有向图的十字链表存储表示 n无向图的邻接多重表存储表示

5、 回答问题 1、什么是图形结构?它和线性结构、树形 结构有何区别? 2、以下图为例,理解图的相关术语,并回 答有关问题。 G1 AB CD AB CD E G2 回答问题 (1)G1中,A到D的路径是什么?路径长 度多少? (2)G2中,A到E的路径是什么?路径长 度多少? (3)G1是强连通图吗?若不是找出其强 连通分量? (4)写出G2的生成树; (5)写出G1的生成森林; 回答问题 (6)写出G1的邻接矩阵、邻接表和十字链表; (7)写出G2的邻接矩阵、邻接表和邻接多重表 。 3、如下所示为一带权有向图,写出其邻接矩阵 、邻接表。 V1V2 V3V4 40 10 50 20 邻接矩阵的结

6、构定义: #define MAX_VERTEX_NUM 20 Typedef enumDG,DN,UDG,UDN Graphkind; typedef struct ArcCell / 弧的定义 VRType adj; / VRType是顶点关系类型。 / 对无权图,用1或0表示相邻否; / 对带权图,则为权值类型。 InfoType *info; / 该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct / 图的定义 VertexType / 顶点信息 vexsMAX_VERTEX_NUM; AdjM

7、atrix arcs; / 弧的信息 int vexnum, arcnum; / 顶点数,弧数 GraphKind kind; / 图的种类标志 MGraph; (1) 矩阵不一定是对称的; (2) 第i 行中1的个数为顶点i 的出度; (3) 第i列中1的个数为顶点 i的入度; (4) 矩阵中1的个数为图中弧的数目; (5) 很容易判断顶点i 和顶点j 是否有弧相连. 从有向图的邻接矩阵可以得出如下结论 从无向图的邻接矩阵可以得出如下结论 (1)矩阵是对称的,可压缩存储(上(下)三角; (2)第i行或第i 列中1的个数为顶点i 的度; (3)矩阵中1的个数的一半为图中边的数目; (4)很容易

8、判断顶点i 和顶点j之间是否有边相连 (看矩阵中i行j列值是否为1)。 容易实现图的操作,如:求某顶点的度、判断顶点 之间是否有边(弧)、找顶点的邻接点等等。仅耗 费 O(1) 时间。 n个顶点需要n*n个单元存储边(弧);空间效率为 O(n2)。对稀疏图而言尤其浪费空间。 邻接矩阵法优点: 邻接矩阵法缺点: 邻接矩阵存储表示特点 邻接表表示 图的邻接表存储方法是一种顺序分配与链式分配相结合 的存储方法,它包括两部分: 一部分是单链表,用来存 放边的信息;另一部分是数组,主要用来存放顶点本身 的数据信息。 表结点 头结点 adjvex nextarc info data firstarc 指示

9、与顶点Vi邻接的 点在图中的位置 指示下一条边 或弧的结点 信息可无 存储顶点Vi的 名或其他信息 指示链表中 第一个结点 从无向图的邻接表可以得到如下结论: (1)第i 个链表中结点数目为顶点i的度; (2)所有链表中结点数目的一半为图中边数; (3)占用的存储单元数目为n+2e 。 从有向图的邻接表可以得到如下结论: (1)第i 个链表中结点数目为顶点i的出度; (2)所有链表中结点数目为图中弧数; (3)占用的存储单元数目为n+e 。 邻接表表示 邻接表表示 邻接表的缺点: 邻接表的优点: 空间效率高;容易寻找顶点的邻接点; 判断任意两顶点间是否有边或弧,需搜索两结 点对应的单链表,没有

10、邻接矩阵方便。 图的邻接表数据类型描述 #define MAXN 50 /*MAXN表示图中最大顶点数*/ typedef struct arcnode /定义边结点的结构 int adjvex; /该弧所指向的顶点的位置 struct arcnode *nextarc ; / 指向下一条弧的指针 InfoType *info; arcnode; typedef struct vnode /定义邻接表的表头类型 VertexType data; /顶点信息 arcnode *firstarc; / 指向第一条依附该顶点的弧 vnode;AdjlistMAXN; 讨论:邻接表与邻接矩阵有什么异同

11、之处? 1. 联系:邻接表中每个链表对应于邻接矩阵中的一行 ,链表中结点个数等于一行中非零元素的个数。 2. 区别: 对于任一确定的无向图,邻接矩阵是唯一的(行列 号与顶点编号一致),但邻接表不唯一(链接次序 与顶点编号无关)。 邻接矩阵的空间复杂度为O(n2),而邻接表的空间复 杂度为O(n+e)。 3. 用途:邻接矩阵多用于稠密图的存储(e接近n(n- 1)/2);而邻接表多用于稀疏图的存储(eadjvex; else return -1; 非连通图的深度优先搜索 若图是非连通的或非强连通图,则从图中某 一个顶点出发。不能用深度优先搜索访问到图中 所有顶点,而只能访问到一个连通子图(既连通

12、 分量)或只能访问到一个强连通子图(既强连通 分量)。这时,可以在每个连通分量或每个强连 通分量中都选一个顶点,进行深度优先搜索遍历 ,最后将每个连通分量或每个强连通分量的遍历 结果合起来,则得到整个非连通图的遍历结果。 遍历算法实现与连通图的只有一点不同,即 对所有顶点进行循环,反复调用连通图的深度优 先搜索遍历算法即可。 2图的广度优先搜索 从图中的某个顶点V0出发,并在访问此顶 点之后依次访问V0的所有未被访问过的邻接点 ,之后按这些顶点被访问的先后次序依次访问 它们的邻接点,直至图中所有和V0有路径相通 的顶点都被访问到。 若此时图中尚有顶点未被访问,则另选图中 一个未曾被访问的顶点作

13、起始点,重复上述过 程,直至图中所有顶点都被访问到为止。 广度优先搜索遍历类似于树的按层次遍历。 设图G的初态是所有顶点均未访问,在G 中任选 一顶点i作为初始点,则广度优先搜索的基本思 想是: (1)首先访问顶点i,并将其访问标志置为 已被访问,即visitedi=1; (2)接着依次访问与顶点i有边相连的所有 顶点W1,W2,Wt; (3)然后再按顺序访问与W1,W2,Wt有 边相连又未曾访问过的顶点; 依此类推,直到图中所有顶点都被访问完 为止 。 void BFSTraverse(Graph G, Status (*Visit)(int v) for (v=0; vadjvex;/*m

14、为u的邻接顶点*/ if (visitedm=0)/*若顶点未标记访问,则递归访问之*/ PathAll(G,m,v,l,path,d); p=p-nextarc/*找u的下一个邻接顶点*/ visitedu=0; /*恢复环境*/ 7.4 图的连通性问题 一、 无向图的连通分量和生成树 若图是连通的或强连通的,则从图中某一个 顶点出发可以访问到图中所有顶点; 若图是非连通的或非强连通图,则需从图中 多个顶点出发搜索访问而每一次从一个新的起始 点出发进行搜索,搜索过程中得到的顶点访问序 列恰为每个连通分量中的顶点集。 DE AB C F J L M GH I K D E GH I K AB C

15、 F J L M 对于连通图, 深度优先搜索遍历算法及广 度优先搜索遍历算法中遍历图过程中历经边的 集合和顶点集合一起构成连通图的极小连通子 图。它是连通图的一棵生成树。 生成树:是一个极小连通子图,它含有图中 全部顶点,但只有n-1条边。 由深度优先搜索遍历得到的生成树,称为 深度优先生成树,由广度优先搜索遍历得到的 生成树,称为广度优先生成树。 1、连通图的生成树 例1 :画出下图的生成树 DFS 生 成 树 v0 v1 v2 v4 v4v3 邻 接 表 0 1 2 3 4 13 341 420 v4 v3 v2 v1 v0 231 420 v0 v2 v1 v4 v3 BFS 生 成 树

16、 v0 v1v3 v2v4 无向连通图 2生成森林 若一个图是非连通图或非强连通图,但有若干 个连通分量或若干个强连通分量,则通过深度优 先搜索遍历或广度优先搜索遍历,不可以得到生 成树,但可以得到生成森林,且若非连通图有 n 个顶点,m 个连通分量或强连通分量,则可以遍 历得到m棵生成树,合起来为生成森林,森林中 包含n-m条树边。 生成森林可以利用非连通图的深度优先搜索 遍历或非连通图的广度优先搜索遍历算法得到。 3 最小生成树 在一般情况下,图中的每条边若给定了权,这 时,我们所关心的不是生成树,而是生成树中边 上权值之和。若生成树中每条边上权值之和达到 最小,称为最小生成树。 构造最小生成树的准则 v必须只使用该网络中的边来构造最小生成树 ; v必须使用且仅使用n-1条边来联结网络中的n 个顶点; v不能使用产生回路的边。 欲在

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 大杂烩/其它

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号