图的抽象数据类型ADT

  1. ADT Graph{
  2.     数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。
  3.     数据关系R：R={VR},VR={<v,w>|v,w属于V且P(v,w),<v,w>表示从v到w的弧，谓词P(v,w)定义了弧<v,w>的意义或信息}
  4.     基本操作P:
  5.     CreateGraph(&G,V,VR)
  6.         初始条件：V是图的顶点集，VR是图中的弧的集合。
  7.         操作结果：按V和VR的定义构造图G。
  8.     DestroyGraph(&G)
  9.         初始条件：图G存在。
  10.         操作结果：销毁图G。
  11.     LocateVex(G,u)
  12.         初始条件：图G存在，u和G中顶点有相同的特征。
  13.         操作结果：若G存在顶点u，则返回该顶点在图中的位置，否则返回其他信息。
  14.     GetVex(G,v)
  15.         初始条件：图G存在，v是G中的某个顶点。
  16.         操作结果：返回v的值。
  17.     PutVet(&G,v,value)
  18.         初始条件：图G存在，v是G中的某个顶点。
  19.         操作结果：对v赋值value。
  20.     FirstAdjVex(G,v)
  21.         初始条件：图G存在，v是G中的某个顶点。
  22.         操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点，则返回空。
  23.     NextAdjVex(G,v,w)
  24.         初始条件：图G存在，v是G中的某个顶点,w是v的邻接顶点。
  25.         操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接顶点，则返回'空'。
  26.     InsertVex(&G,v)
  27.         初始条件：图G存在，v和图中顶点具有相同特征。
  28.         操作结果：在图中增加新顶点v。
  29.     DeleteVex(&G,v)
  30.         初始条件：图G存在，v是G中的某个顶点。
  31.         操作结果：删除G中顶点v及其相关的弧。
  32.     InsertArc(&G,v)
  33.         初始条件：图G存在，v和w是G中的两个顶点。
  34.         操作结果：在G中增添<v,w>,若G是无向的，则还增添对称弧<w,v>。
  35.     DeleteAec(&G,v)
  36.         初始条件：图G存在，v和w是G中的两个顶点。
  37.         操作结果：在G中删除<v,w>,若G是无向的，则还删除对称弧<w,v>。
  38.     DFCTraverse(G,Visit())
  39.         初始条件：图G存在，Visit是顶点应用函数。
  40.         操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦Visit失败，则操作失败。
  41.     BFCTraverse(G,Visit())
  42.         初始条件：图G存在，Visit是顶点应用函数。
  43.         操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦Visit失败，则操作失败。
  44. }ADT Graph