1/31
文档分类:法律/法学

(第十三讲).ppt


下载后只包含 1 个 PPT 格式的文档,里面的视频和音频不保证可以播放,查看文件列表

特别说明:文档预览什么样,下载就是什么样。

0/100
您的浏览器不支持进度条
下载所得到的文件列表
(第十三讲).ppt
文档介绍:
(第十三讲)绍兴文理学院计算机系计算机应用教研室数据结构数据的多对多 关系是怎样 建立的?第6章图(1)一、教学目的:明确图的有关概念、结构特点和抽象数据类型;掌握图的数组表示法和邻接表表示法;掌握建立图存储结构的基本算法;了解图的十字链表和邻接多重表表示法。二、教学重点:图的有关概念、结构特点;图的数组表示法和邻接表表示法;建立图存储结构的基本算法;三、教学难点:图的有关概念;图的邻接表表示法;建立图存储结构的基本算法;四、教学过程:§6.1.0关于图1、数据对象的“多对多”关系---图结构每个元素可以有零个或多个直接前趋;零个或多个直接后继;2、应用广泛§6.1图的定义和基本术语§6.1.1图的定义1、概念(1)定义图(Graph)G由两个集合V和E组成,记为G=(V,E),其中V(Vertex)是顶点的有穷非空集合记为V(G),E(Edge)是V中顶点偶对的有穷集E(G)。(2)有向图与无向图①有向图:对于图G,若边集E(G)为有向边的集合,则称该图为有向图;最省线路问题,最小工程计划问题等。最短路径问题,V1V5V4V2V3V1V2V3V4TKS**因此,<x,y>与<x,y>是不同的两条边。顶点对用一对尖括号括起来,x是有向边的始点,y是有向边的终点。<x,y>也称作一条弧,则x为弧尾,y为弧头。如图G1G1=(V1,E1)V1={v1,v2,v3,v4}E1={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}②无向图:对于图G,若边集E(G)为无向边的集合,则祢该图为无向图。在无向图中,顶点对(x,y)是无序的,它称为与顶点x和顶点y相关联的一条边。这条边没有特定的方向,(x,y)与(y,x)是同一条边。V1V2V3V4有向图G1V1V5V4V2V3无向图G2如图G2G2=(V2,E2)V2={v1,v2,v3,v4,v5}E2={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4)(v3,v5)}TKS**2、抽象数据类型定义ADTGraph{数据对象V:V是具有相同特性的数据元素的集合,称为顶点集。数据关系R:R={VR}VR={<V,W>︱V,W∈V且P(V,W),<V,W>表示从V到W的弧,谓词P(V,W)定义了弧<V,W>的意义或信息}基本操作P:CreateGraph(&G,V,VR);初始条件:V是图的顶点集,VR是图中弧的集合。操作结果:按V和VR的定义构造图G。DFSTraverse(G,v,Visit());初始条件:图G存在,v是G中某个顶点,Visit是顶点的应用函数。V1V2V3V4有向图G1V1V5V4V2V3无向图G2TKS**操作结果:从顶点v起深度优先遍历图G,并对每个顶点调用函数Visit一次且仅一次。一旦Visit()失败,则操作失败。BFSTraverse(G,v,Visit());初始条件:图G存在,v是G中某个顶点,Visit是顶点的应用函数。操作结果:从顶点v起广度优先遍历图G,并对每个顶点调用函数Visit一次且仅一次。一旦Visit()失败,则操作失败。}ADTGraph§6.1.2图的基本术语约定:用n表示图中的顶点数,e表示边或弧的数目,且若<vi,vj>∈VR,则vi≠vj。V1V2V3V4有向图G1V1V5V4V2V3无向图G21、子图:对于G=(V,E)和G’=(V’,E’),如果V’V且E’E则称G’为G的子图。TKS**2、无向完全图和有向完全图:若e=n(n-1)/2的无向图则称为无向完全图。若e=n(n-1)的有向图则称为有向完全图。3、稀疏图和稠密图:有很少条边或弧(如e<nlogn)的图称为稀疏图,反之称为稠密图。4、权和网:与图的边或弧相关的数叫做权。带权的图称为网。5、邻接点:对于无向图G=(V,E),如果边(v,v’)∈E,则称顶点v和v’互为邻接点,即v和v’相邻接。边(v,v’)依附于顶点v和v’。边(v,v’)与顶点v和v’相关联。V1V2V3V4有向图G1V1V5V4V2V3无向图G2TKS**6、度、入度和出度顶点v的度是和v相关联的边的数目,记为TD(v)。顶点v的入度是以顶点v为头的弧的数目,记为ID(v)。顶点v的出度是以顶点v为尾的弧的数目,记为OD(v)。顶点v的度为TD(v)=ID(v)+OD(v)。显然有V1V2V3V4有向图G1V1V5V4V2V3无向图G27、路径和路径长度(1)路径:无向图G=(V,{E})中从顶点v到顶点v’的路径是一个顶点序列(v=vi0,vi1,…vim=v’),其中(vij-1,vij)∈E,1≤j≤m。若G是有向图,则路径也是有向的,顶点序列应满足<vij-1,vij>∈E,1≤j≤m。TKS**8、回路或环第一个顶点和最后一个顶点相同的路径 内容来自淘豆网www.taodocs.com转载请标明出处.
更多>> 相关文档
非法内容举报中心
文档信息
  • 页数31
  • 收藏数0 收藏
  • 顶次数0
  • 上传人1387228****
  • 文件大小812 KB
  • 时间2020-08-01
文档标签