图Graph是种较线性表和树更为复杂的数据结构在线性.ppt

第7章 图 图(Graph)是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素(即其孩子结点)相关，但只能和上一层中一个元素(即其双亲结点)相关；而在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。 主要学习图的存储结构以及若干图的操作的实现。 7.1 图的定义和术语 （1学时） 图是一种数据结构，加上一组基本操作，就构成了抽象数据类型。抽象数据类型图的定义如下： ADT Graph{ 数据对象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。 DestroyGraph(G)； 初始条件：图G存在。 操作结果：销毁图G。 LocateVex(G，u)； 初始条件：图G存在，u和G中顶点有相同特征。 操作结果：若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的第一个邻接顶点。若顶点在G中 没有邻接顶点，则返回“空”。 NextAdjVex(G，v，w)； 初始条件：图G存在，v是G中某个顶点， w是v的邻接顶点。 操作结果：返回v的(相对于w的)下一个邻接顶点。 若w是v的最后一个邻接点，则返回“空”。 InsertVex(G，v)； 初始条件：图G存在，v和图中顶点有相同特征。 操作结果：在图G中增添新顶点v。 DeleteVex(G，v)； 初始条件：图G存在，v是G中某个顶点。 操作结果：删除G中顶点v及其相关的弧。 InsertArc(G，v，w)； 初始条件：图G存在，v和w是G中两个顶点。 操作结果：在G中增添弧v，w， 若G是无向的则还增添对称弧w，v。 DeleteArc(G，v，w)； 初始条件：图G存在，v和w是G中两个顶点。 操作结果：在G中删除弧v，w， 若G是无向的则还删除对称弧w，v。 DFSTraverse (G，v，Visit())； 初始条件：图G存在，v是G中某个顶点， Visit是顶点的应用函数。 操作结果：从顶点v起深度优先遍历图G， 并对每个顶点调用函数Visit一次且仅一次。 BFSTraverse (G，v，Visit())； 初始条件：图G存在，v是G中某个顶点， Visit是顶点的应用函数。 操作结果：从顶点v起广度优先遍历图G， 并对每个顶点调用函数Visit一次且仅一次。 }ADT Graph 在图中的数据元素通常称做顶点(Vertex)，V是顶