（第十三讲）.ppt

(第十三讲)绍兴文理学院计算机系计算机应用教研室数据结构数据的多对多关系是怎样建立的?第6章图(1)一、教学目的:明确图的有关概念、结构特点和抽象数据类型;掌握图的数组表示法和邻接表表示法;掌握建立图存储结构的基本算法;了解图的十字链表和邻接多重表表示法。二、教学重点:图的有关概念、结构特点;图的数组表示法和邻接表表示法;建立图存储结构的基本算法;三、教学难点:图的有关概念;图的邻接表表示法;建立图存储结构的基本算法;四、教学过程:§、数据对象的“多对多”关系---图结构每个元素可以有零个或多个直接前趋;零个或多个直接后继;2、应用广泛§§、概念(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§:用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、回路或环第一个顶点和最后一个顶点相同的路径