敦黎 第七章图 程序设计—数据结构 图的遍历算法及其应用 操作结果：若G中存在顶点u,则返回该项点在图中位置，否则返回其 它信息 GetVex(G.v) 初始条件：图G存在，v是G中某个顶点 操作结果：返回ⅴ的值 PutVex(&G,v,value) 初始条件：图G存在，v是G中某个顶点 操作结果：对v赋值value FirstAdjVex(G,v) 初始条件：图G存在，V是G中某个顶点 操作结果：返回ⅴ的第一个邻接顶点。若顶点在G中没有邻接顶点，则 返回“空” NextAdjVex(G,v,w) 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点 操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的最后一 个邻接点，则返回“空” InsertVex(&G.v) 初始条件：图G存在，ⅴ和G中顶点有相同特征 操作结果：在图中增添新顶点ⅴ Delete Vex(&G,v) 初始条件：图G存在，ⅴ是G中某个顶点 操作结果：删除G中顶点V及其相关的弧 InsertArc(&G,v,w) 初始条件：图G存在，v和w是G中两个顶点 操作结果：在图G中增添弧<，w>,若G是无向的，则还应增添对称弧 <w,V> DeleteArc(&G,v,w) 初始条件：图G存在，v和w是G中两个顶点 操作结果：删除G中的弧<V,w心，若G是无向的，则还应删除对称弧 DFSTraverse(G,v,visit()) 初始条件：图G存在，v是G中某个顶点，vsit是对顶点的应用函数 操作结果：从顶点v起深度优先遍历图G,并对每个顶点调用函数visit() 一次且至多一次。一旦visit()失败，则操作失败 BFSTraverse(G,v,visit()) 初始条件：图G存在，v是G中某个顶点，vsit是对顶点的应用函数 操作结果：从顶点v起广度优先遍历图G,并对每个顶点调用函数visit() 一次且至多一次。一旦visit()失败，则操作失败 ADT Graph 7.2图的存储和创建 7.2.1图的存储表示 1、图的存储表示分析 ,顶点之间的关系是多对多的(m:n),由于m和n都是不定的，无法给出一个这种多对多 的关系向线性关系的映射公式 ∴图中的关系不能通过顺序映像（即通过顶点之间的存储位置反映顶点之间的逻辑关系）反 文档编号 完成时间 完成人张昱 修改时间20026-6 第2页程序设计——数据结构 第七章 图 图的遍历算法及其应用 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 2 页 操作结果：若 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 是无向的，则还应删除对称弧 DFSTraverse(G, v, visit( )) 初始条件：图 G 存在，v 是 G 中某个顶点，visit 是对顶点的应用函数 操作结果：从顶点 v 起深度优先遍历图 G，并对每个顶点调用函数 visit( ) 一次且至多一次。一旦 visit( )失败，则操作失败 BFSTraverse(G, v, visit( )) 初始条件：图 G 存在，v 是 G 中某个顶点，visit 是对顶点的应用函数 操作结果：从顶点 v 起广度优先遍历图 G，并对每个顶点调用函数 visit( ) 一次且至多一次。一旦 visit( )失败，则操作失败 }ADT Graph 7.2 图的存储和创建 7.2.1 图的存储表示 1、图的存储表示分析 ∵顶点之间的关系是多对多的(m : n)，由于 m 和 n 都是不定的，无法给出一个这种多对多 的关系向线性关系的映射公式 ∴图中的关系不能通过顺序映像(即通过顶点之间的存储位置反映顶点之间的逻辑关系)反