PowerPoint Presentation - 华中师范大学.ppt_第1页
PowerPoint Presentation - 华中师范大学.ppt_第2页
PowerPoint Presentation - 华中师范大学.ppt_第3页
PowerPoint Presentation - 华中师范大学.ppt_第4页
PowerPoint Presentation - 华中师范大学.ppt_第5页
已阅读5页,还剩54页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、2020/8/7,1,第7章 图,本章主题:图的基本概念、图的存储结构和图的常用算法 教学目的: 教学重点:图的各种存储方式及其运算 教学难点:图结构存储方式的选择,几种经典图算法的实现 本章内容:图的基本概念 图的存储结构 图的遍历 最小生成树 最短路径 拓扑排序 关键路径,2020/8/7,2,本章主要介绍图的基本概念、图的存储结构和有关图的一些常用算法。通过本章学习,读者应该: 1) 了解图的定义和术语 2) 掌握图的各种存储结构 3) 掌握图的深度优先搜索和广度优先搜索遍历算法 4) 理解最小生成树、最短路径、拓扑排序、关键路径等图的常用算法,本章学习导读,2020/8/7,3,图(G

2、raph)是一种较线性表和树更为复杂的非线性结构。是对结点的前趋和后继个数不加限制的数据结构,用来描述元素之间“多对多”的关系。 在线性结构中,结点之间的关系是线性关系,除开始结点和 终端结点外,每个结点只有一个直接前趋和直接后继。 在树形结构中,结点之间的关系实质上是层次关系,同层上的每个结点可以和下一层的零个或多个结点(即孩子)相关,但只能和上一层的一个结点(即双亲)相关(根结点除外)。 在图结构中,对结点(图中常称为顶点)的前趋和后继个数不加限制的,即结点之间的关系是任意的。 由此,图的应用极为广泛,特别是近年来的迅速发展,已渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及

3、数学的其它分支中。,2020/8/7,4,7. 1 .1 图的定义 图是由一个顶点集 V 和一个弧集 R构成的数据结构。 Graph = (V, R ) V = x | x 某个数据对象 , 是顶点的有穷非空集合; R边的有限集合 R = (x, y) | x, y V 无向图 或 R = | x, y V /邻接矩阵类型 typedef struct VertexType vexsMAX_VERTEX_NUM; /顶点表 AdjMatrix arcs; /邻接矩阵 int vexnum,arcnum; /图的顶点数和弧数 MGraph; 由于一般图的边或弧较少,其邻接矩阵的非零元素较少,属稀

4、疏矩阵,因此会造成一定存储空间的浪费。,2020/8/7,24,7.2.2 邻接表 图的链式存储结构 1) 为每个顶点建立一个单链表, 2) 第i个单链表中包含顶点Vi的所有邻接顶点。 邻接表是图的一种链式存储结构。类似于树的孩子链表表示法。在邻接表中为图中每个顶点建立一个单链表,用单链表中的一个结点表示依附于该顶点的一条边(或表示以该顶点为弧尾的一条弧),称为边(或弧)结点。,2020/8/7,25,把同一个顶点发出的边链接在同一个边链表中,链表的每一个结点代表一条边,叫做表结点(边结点),邻接点域adjvex保存与该边相关联的另一顶点的顶点下标 , 链域nextarc存放指向同一链表中下一

5、个表结点的指针 ,数据域info存放边的权。边链表的表头指针存放在头结点中。头结点以顺序结构存储,其数据域data存放顶点信息,链域firstarc指向链表中第一个顶点。,2020/8/7,26,带权图的边结点中info保存该边上的权值 。 顶点 Vi 的边链表的头结点存放在下标为 i 的顶点数组中。 在邻接表的边链表中,各个边结点的链入顺序任意,视边结点输入次序而定。,2020/8/7,27,有向图的邻接表和逆邻接表,在有向图的邻接表中,第 i 个链表中结点的个数是顶点Vi的出度。 在有向图的逆邻接表中,第 i 个链表中结点的个数是顶点Vi 的入度。,2020/8/7,28,图7-7 为图7

6、-6 (a)的的邻接表和逆邻接表,图7-7 有向图的邻接表和逆邻接表,7-6 (a),(b),4,1,3,2,0,2,1,2,3,1,0,1,2,3,(c),1,4,3,2,1,3,0,0,3,2,0,1,2,3,2020/8/7,29,网络 (带权图) 的邻接表,2020/8/7,30,存储表示 typedef struct ArcNode int adjvex; struct ArcNode *nextarc; int info; ArcNode; /边结点类型 typedef struct VNode VertexType data; ArcNode *firstarc; VNode,A

7、djListMAX_VERTEX_NUM; typedef struct AdjList vertices; /邻接表 int vexnum,arcnum; ALGraph;,2020/8/7,31,7.2.3 十字链表 十字链表 (Orthogonal List)是有向图的另一种链式存储结构。可看作是将有向图的邻接表和逆邻接表结合的一种链表。 在十字链表中,为每个顶点vi设置一个结点,它包含数据域data和两个链域firstout、firstin,称为顶点结点。数据域data用于存放顶点vi的有关信息;链域firstin指向以顶点vi为弧头的第一个弧结点;链域firstout指向以顶点vi为

8、弧尾的第一个弧结点。 弧结点包括四个域:尾域tailvex、头域headvex,链域hlink和tlink。 hlink指向弧头相同的下一条弧,tlink指向弧尾相同的下一条弧;data顶点信息,firstin以该顶点为头的第一个弧结点,firstout以该结点为尾的第一个弧结点,顶点结点,弧结点,2020/8/7,32,图7-8 十字链表,图7-8为图7-6 (a)有向图的十字链表。,采用十字链表表示有向图,很容易找到以顶点vi为弧尾的弧和以顶点vi为弧头的弧,因此顶点的出度、入度都很容易求得。,2020/8/7,33,十字链表的数据类型定义如下: #define MAXV typedef

9、struct /弧结点 int tailvex,headvex; /弧尾和弧头顶点位置 struct ArcNode *hlink,*tlink; /弧头相同和弧尾相同的弧的链域 ArcNode; typedef struct /顶点结点 VertexType data; /顶点信息 ArcNode *firstin,*firstout; /分别指向该顶点的第一条入弧和出弧 VexNode;,2020/8/7,34,7.2.4 邻接多重表 邻接多重表是无向图的另一种链式存储结构。在邻接多重表中设置一个边结点表示图中的一条边。边结点包含五个域,结构如下所示:,其中:mark 域 标志域,用于对该

10、边进行标记; ivex 域 存放该边依附的一个顶点vi的位置信息; ilink 域 该链域指向依附于顶点vi的另一条边的边结点; jvex 域 存放该边依附的另一个顶点vj的位置信息; jlink 域 该链域指向依附于顶点vj的另一条边的边结点。 邻接多重表为每个顶点设置一个结点,其结构如下:,2020/8/7,35,图7-9 邻接多重表,图7-9为图7-5 (a)无向图的邻接多重表。,由邻接多重表可以看出,表示边(vi,vj)的边结点通过链域ilink和jlink链入了顶点vi和顶点vj的两个链表中,实现了用一个边结点表示一个边的目的,克服了在邻接表中用两个边结点表示一个边的缺点。因此邻接多

11、重表是无向图的一种很有效的存储结构。,2020/8/7,36,邻接多重表的结点数据类型定义如下: #define MAXV typedef struct /边结点类型 int mark; /访问标识 int ivex,jvex; /该边的两个顶点位置信息 struct Enode *ilink,*jlink; /分别指向依附这两个顶点的下一条边 Enode; typedef struct /顶点结点类型 VertexType data; /顶点数据域 ENode *firstedge; /指向第一条依附该顶点的边 Vnode;,2020/8/7,37,7.3 图的遍历,和树的遍历相似,若从图中

12、某顶点出发访遍图中每个顶点,且每个顶点仅访问一次,此过程称为图的遍历。 (Traversing Graph)。 但是,在图中有回路,从图中某一顶点出发访问图中其它顶点时,可能又会回到出发点,而图中或许还有顶点没有访问到,因此,图的遍历较树的遍历更复杂。 图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。 图的遍历顺序有两种:深度优先搜索(DFS)和广度优先搜索(BFS)。对每种搜索顺序,访问各顶点的顺序也不是唯一的。,2020/8/7,38,7.3.1 深度优先搜索(DFS) 1 深度优先搜索思想 深度优先搜索遍历类似于树的先序遍历。假定给定图G的初态是所有顶点均未被访问过,

13、在G中任选一个顶点i作为遍历的初始点,则深度优先搜索递归调用包含以下操作: (1)访问搜索到的未被访问的邻接点; (2)将此顶点的visited数组元素值置1; (3)搜索该顶点的未被访问的邻接点,若该邻接点存在,则从此邻接点开始进行同样的访问和搜索。 深度优先搜索DFS可描述为: (1)访问v0顶点; (2)置 visitedv0=1; (3)搜索v0未被访问的邻接点w,若存在邻接点w,则DFS(w)。,2020/8/7,39,遍历过程: DFS 在访问图中某一起始顶点 v 后,由 v 出发,访问它的任一邻接顶点 w1;再从 w1 出发,访问与 w1邻 接但还没有访问过的顶点 w2;然后再从

14、 w2 出发,进行类似的访问, 如此进行下去,直至到达所有的邻接顶点都被访问过的顶点 u 为止。 接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。重复上述过程,直到连通图中所有顶点都被访问过为止。,2020/8/7,40,深度优先搜索的示例,图中可能存在回路,且图的任一顶点都可能与其它顶点相通,在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。 为了避免重复访问,可设置一个标志顶点是否被访问过的辅助数组 visited ,它的初始状态为 0,在图的遍历过程中

15、,一旦某一个顶点 i 被访问,就立即让 visited i 为 1,防止它被多次访问。,2020/8/7,41,对上图,深度优先搜索遍历的顺序(之一)为: v1 v2v4 v8 v5v6v3v7。,图7-10 深度优先搜索,2020/8/7,42,深度优先搜索算法: int visitedMAX_VERTEX_NUM; void DFS(ALGraph G, int v) ArcNode *p; printf(%c,G.verticesv.data); visitedv=1; p=G.verticesv.firstarc; while (p) if (!visitedp-adjvex) DFS

16、(G,p-adjvex); p=p-nextarc; /从第v个顶点出发DFS,2020/8/7,43,整个图的DFS遍历 void DFSTraverse(ALGraph G) for (int v=0;vG.vexnum;+v) visitedv=0; for (v=0;vG.vexnum;+v) if (!visitedv) DFS(G,v); 对于连通图,从一个顶点出发,调用DFS函数即可将所有顶点都遍历到。,2020/8/7,44,7.3.2 广度优先搜索(BFS) 1 广度优先搜索思想 广度优先搜索遍历类似于树的按层次遍历。 对于无向连通图,广度优先搜索是从图的某个顶点v0出发,在

17、访问v0之后,依次搜索访问v0的各个未被访问过的邻接点w1,w2,。然后顺序搜索访问w1的各未被访问过的邻接点,w2的各未被访问过的邻接点,。即从v0开始,由近至远,按层次依次访问与v0有路径相通且路径长度分别为1,2,的顶点,直至连通图中所有顶点都被访问一次。 广度优先搜索的顺序不是唯一的,例如图7-10 (a) 连通图的广度优先搜索遍历顺序可为v1,v2,v3,v4,v5,v6,v7,v8 也可为v1,v3,v2,v7,v6,v5,v4,v8。,2020/8/7,45,1 广度优先搜索思想 设图G的初态是所有顶点均未访问,在G 中任选一顶点i作为初始点,则广度优先搜索的基本思想是: (1)

18、从图中的某个顶点V出发,访问之;并将其访问标志置为已被访问,即visitedi=1; (2)依次访问顶点V的各个未被访问过的邻接 点,将V的全部邻接点都访问到; (3)分别从这些邻接点出发,依次访问它们的未被访问过的邻接点,并使“先被访问的顶 点的邻接点”先于“后被访问的顶点的邻接 点”被访问,直到图中所有已被访问过的顶 点的邻接点都被访问到。 依此类推,直到图中所有顶点都被访问完为止 。,2020/8/7,46,广度优先搜索在搜索访问一层时,需要记住已被访问的顶点,以便在访问下层顶点时,从已被访问的顶点出发搜索访问其邻接点。所以在广度优先搜索中需要设置一个队列Queue,使已被访问的顶点顺序

19、由队尾进入队列。在搜索访问下层顶点时,先从队首取出一个已被访问的上层顶点,再从该顶点出发搜索访问它的各个邻接点。,广度优先搜索过程 广度优先生成树,广度优先搜索的示例,2020/8/7,47,7.4 最小生成树,1. 生成树 在一个无向连通图G中,其所有顶点和遍历该图经过的所有边所构成的子图G 称做图G的生成树。一个图可以有多个生成树,从不同的顶点出发,采用不同的遍历顺序,遍历时所经过的边也就不同,例如图7-12的(b) 和(c) 为图7-12 (a) 的两棵生成树。其中 (b) 是通过DFS得到的,称为深度优先生成树;(c) 是通过BFS得到的,称为广度优先生成树。,图7-12 生成树,20

20、20/8/7,48,按照生成树的定义,n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。而所有包含n-1 条边及n个顶点的连通图都是无回路的树,所以生成树是连通图中的极小连通子图. 由于使用不同的遍历图的方法,可以得到不同的生成树;从不同的顶点出发,也可能得到不同的生成树。如深度优先生成树、广度优先生成树 在图论中,常常将树定义为一个无回路连通图。 对于一个带权的无向连通图,其每个生成树所有边上的权值之和可能不同,我们把所有边上权值之和最小的生成树称为图的最小生成树。求图的最小生成树有很多实际应用。例如,通讯线路铺设造价最优问题就是一个最小生成树问题。,2020/8/7,49,假设把n

21、个城市看作图的n个顶点,边表示两个城市之间的线路,每条边上的权值表示铺设该线路所需造价。铺设线路连接n个城市,但不形成回路,这实际上就是图的生成树,而以最少的线路铺设造价连接各个城市,即求线路铺设造价最优问题,实际上就是在图的生成树中选择权值之和最小的生成树。构造最小生成树的算法有很多,下面分别介绍克鲁斯卡尔(Kruskal)算法和普里姆(Prim)算法。,7.4.1 克鲁斯卡尔(Kruskal)算法 克鲁斯卡尔算法是一种按权值递增的次序选择合适的边来构造最小生成树的方法。,2020/8/7,50,算法的基本思想: 在图中任取一个顶点K作为开始点,令U=k,W=V-U,其中V为图中所有顶点集,

22、然后找一个顶点在U中,另一个顶点在W中的边中最短的一条,找到后,将该边作为最小生成树的树边保存起来,并将该边顶点全部加入U集合中,并从W中删去这些顶点,然后重新调整U中顶点到W中顶点的距离, 使之保持最小,再重复此过程,直到W为空集止。 假设G=(V,E)是一个具有n个顶点的带权无向连通图,T= (U,TE)是G的最小生成树,其中U是T的顶点集,TE是T的边集,则构造最小生成树的过程如下: (1) 置U的初值等于V,TE的初值为空集; (2) 按权值从小到大的顺序依次选取图G中的边,若选取的边未使生成树T形成回路,则加入TE;若选取的边使生成树T形成回路,则将其舍弃。循环执行(2),直到TE中

23、包含(n-1)条边为止。,2020/8/7,51,应用克鲁斯卡尔算法构造最小生成树的过程:,2020/8/7,52,7.5 最短路径,交通网络中常常提出这样的问题:从甲地到乙地之间是否有公路连通? 在有多条通路的情况下,哪一条路最短? 交通网络可用带权图来表示。顶点表示城市名称,边表示两个城市有路连通,边上权值可表示两城市之间的距离、交通费或途中所花费的时间等。求两个顶点之间的最短路径,不是指路径上边数之和最少,而是指路径上各边的权值之和最小。 另外,若两个顶点之间没有边,但有可能有间接通路(从其它顶点达到)。 路径上的开始顶点(出发点)称为源点,路径上的最后一个顶点称为终点,并假定讨论的权值

24、不能为负数。,2020/8/7,53,最短路径: 如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条,如何找到一条路径使得沿此路径上各边上的权值总和达到最小。 对于带权的图,通常把一条路径上所经过边或弧上的权值之和定义为该路径的路径长度。从一个顶点到另一个顶点可能存在着多条路径,把路径长度最短的那条路径称为最短路径,其路径长度称为最短路径长度。无权图实际上是有权图的一种特例,我们可以把无权图的每条边或弧的权值看成是l,每条路径上所经过的边或弧数即为路径长度。本章讨论两种最常见的最短路径问题。,2020/8/7,54,问题解法 边上权值非负情形的单源最短路径问题 Dijks

25、tra算法 所有顶点之间的最短路径 Floyd算法 边上权值非负情形的单源最短路径问题 问题的提法: 给定一个带权有向图D与源点v,求从v到D中其它顶点的最短路径。限定各边上的权值大于或等于0。 为求得这些最短路径,Dijkstra提出按路径长度的递增次序,逐步产生最短路径的算法。首先求出长度最短的一条最短路径,再参照它求出长度次短的一条最短路径,依次类推,直到从顶点v到其它各顶点的最短路径全部求出为止。,2020/8/7,55,7.5.1 求一顶点(单源点)到其余顶点的最短路径 单源点最短路径是指:给定一个出发点(单源点)和一个有向网G=(V,E),求出源点到其它各顶点之间的最短路径。 迪杰斯特拉(Dijkstra)在做了大量观察后,首先提

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论