图的基本操作

根据图的定义可知,图的顶点之间没有先后次序之分,图中任一顶点都可看成是第一顶点,而且任一顶点的邻接点也不存在确定的顺序。为了操作方便,可将图的顶点按某种顺序排列,由此即可得到顶点的位置(或序号)。同样也可把每个顶点的邻接点进行排列,便可得到第一邻接点、第二邻接点等。在上述人为约定的基础上,可对图进行一些常用的基本操作。

图的基本操作定义如下:

  • CreatGraph(G):输入图的顶点和边,建立图 G 的存储。

  • DestroyGraph(G):释放图占用的存储空间。

  • GetVertex(G, vi):在图中找到顶点 vi,并返回顶点 vi的相关信息。

  • AddVertex(G, vi):在图中增添新顶点 vi

  • DelVertex(G, vi):在图中删除顶点 v 及所有和顶点 v 相关联的边或弧。

  • AddArc(G, vi, vj):在图中增添一条从顶点 vi到顶点 vj 的边或弧。

  • DelArc(G, vi, vj):在图中删除一条从顶点 vi 到顶点 vj 的边或弧。

  • DFS(G, vi):在图中从顶点 vi 出发深度优先遍历图。

  • BFS(G, vi):在图中从顶点 vi 出发广度优先遍历图。

在一个图中,顶点是没有先后次序的,但当采用某一种确定的存储方式存储后,存储结构中顶点的存储次序构成了顶点之间的相对次序,这里用顶点在图中的位置表示该顶点的存储顺序;同样的道理,对一个顶点的所有邻接点,采用该顶点的第 i 个邻接点表示与该顶点相邻接的某个顶点的存储顺序。在这种意义下,图的基本操作还有:

  • LocateVertex(G, vi):在图中找到顶点 vi,返回该顶点存储向量的下标,也称序号。

  • FirstAdjVertex(G, vi):在图中返回 vi 的第一个邻接点。若顶点在图中没有邻接顶点,则返回「空」。

  • NextAdjVertex(G, vi, vj):在图中返回 vi 的(相对于 vj 的)下一个邻接顶点。若 vj 是 vi 的最后一个邻接点,则返回「空」。

用户头像
登录后发表评论