图数据结构课件.ppt

《图数据结构课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图的定义和基本术语图的存储结构图的遍历生成树最短路径第七章图图的定义和基本术语一、图的定义本章介绍另一种非线性数据结构—图,主要学习图的存储结构以及图的若干操作的实现。图是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继。图G由两个集合构成，记作G=(V,{A})其中V是顶点的非空有限集合，A是边的有限集合，其中边是顶点的无序对或有序对(此时的图称为无向图或有向图)。无向图G1=(V1,{A1})，V1={v0,v1,v2,v3,v4}，A1={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3),(v2,v4)}无序对(vi

2、,vj)：用连接顶点vi、vj的线段表示，称为无向边；G1图示V0V4V3V1V2有序对：用以为vi起点(弧尾)、以vj为终点(弧头)的有向线段表示，称为有向边或弧；G2图示V0V1V2V3有向图G2=(V2,{A2})，V2={v0v1,v2,v3}，A2={,,,}例1交通图（公路、铁路）顶点：地点边：连接地点的路交通图中的有单行道、双行道，分别用有向边、无向边表示；例2电路图顶点：元件边：连接元件之间的线路例3通讯线路图顶点：地点边：地点间的连线例4各种流程图(如生产流程图)顶点：工序边：各道工序之间的

3、顺序关系V0V4V3V1V2V0V1V2V3图的实例ADTGraph{数据对象V:V是具有相同特性的数据元素的集合，称为顶点集。ADT图的定义基本操作:CreateGraph(&G,V,VR)//按定义构造图初始条件:V是图的顶点集,VR是图中弧的集合。操作结果:按V和VR的定义构造图G。数据关系R:R={VR}VR={︱v,wV，且p(v,w),表示从v到w的弧，谓词p(v,w)定义了弧的意义或信息。}DestroyGraph(&G)//销毁初始条件:图G存在。操作结果:销毁图G。LocateVex(G,u)//定位初始条件:图G存在，u和G中

4、顶点有相同特性。操作结果:若G中存在顶点u，则返回该顶点在图中位置；否则返回其它信息。GetVex(G,v)//求值初始条件:图G存在，v是G中某个顶点。操作结果:返回v的值。PutVex(&G,v,value)//赋值初始条件:图G存在，v是G中某个顶点。操作结果:对v赋值value。FirstAdjVex(G,v)//求第一个邻接点初始条件:图G存在，v是G中某个顶点。操作结果:返回v的第一个邻接点。若顶点v在G中没有邻接顶点，则返回“空”。NextAdjVex(G,v,w)//求下一个邻接点初始条件:图G存在，v是G中某个顶点，w是v的邻接点。操作结果:返回v的（相对于w

5、的）下一个邻接点。若w是v的最后一个邻接点，则返回“空”。InsertVex(&G,v);//插入顶点初始条件:图G存在，v和G中顶点有相同特性。操作结果:在图G中增添新顶点v。DeleteVex(&G,v)//删除顶点初始条件:图G存在，v和G中顶点有相同特性。操作结果:删除G中顶点v及其相关的弧。InsertArc(&G,v,w)//插入弧初始条件:图G存在，v和w是G中两个顶点。操作结果:在G中增添弧，若G是无向的，则还增添对称弧。DeleteArc(&G,v,w)//删除弧初始条件:图G存在，v和w是G中两个顶点。操作结果:在G中删除弧，若

6、G是无向的，则还删除对称弧。DFSTraverse(G,v,Visit())//深度优先遍历初始条件:图G存在，v是G中某个顶点，Visit()是顶点的应用函数。操作结果:从顶点v起深度优先遍历图G，并对每个顶点调用函数Visit()一次且仅一次。一旦Visit()失败，则操作失败。BFSTraverse(G,v,Visit())//广度优先遍历初始条件:图G存在，v是G中某个顶点，Visit()是顶点的应用函数。操作结果:从顶点v起广度优先遍历图G，并对每个顶点调用函数Visit()一次且仅一次。一旦Visit()失败，则操作失败。2顶点的度、入度、出度顶点v的度T

7、D(v)=与v相关联的边的数目。在有向图中：顶点v的出度OD(v)=以v为起点有向边数；顶点v的入度ID(v)=以v为终点有向边数；TD(v)=OD(v)+ID(v)V0V4V3V1V2V0V1V2V3二、图的基本术语1邻接点及关联边邻接点：边的两个顶点；关联边：若边e=(v,u),则称边e与顶点v和u相关联；设图G的顶点数为n，边数为e则图的所有顶点的度数之和=2*e（每条边对图的所有顶点的度数之和“贡献”2度）无向图G1有向图G2V0V4V3V1V2V0V1V2V3路径、回路(环)无向图