图的基本操作

在本章的开篇已经提到，图中结点间的关系是任意的。线性表和树都有唯一确定的“第一个”结点，按照某种逻辑定义，我们可以从这个结点开始，将线性表和树中的结点作一个排序。然而根据图的逻辑定义，图中并不存在一个完全的次序，即不能按照定义像线性表和树一样给图中的数据排序。但图中也存在增加、删除、修改这些基本操作。为了使这些操作有个明确的定义，我们需要图中的顶点在图中有一个位置的概念。

为了操作方便，人为地将这些结点随意编号，同时将图中某个顶点的多个邻接点随意排序。根据这种并不遵循任何规律与定理的、完全人为的排序，我们认为，在这个排序中，对于一个图，出现了第一个或第k个顶点；对于某一个顶点，出现了第一个或第k个邻接点。若对于某个顶点，出现了第k+1个邻接点，则称第k+1个邻接点为第k个邻接点的下一个邻接点；若这个顶点的邻接点的数目为n，可认为第n个邻接点的下一个邻接点为空。

下面列出图的几种基本操作。

● 创建-CreateGraph (*G,V,VR)：创建一个新的图G。

● 销毁-DestoryGraph (*G)：若图G存在，则销毁图G。

● 顶点位置-VextexLocation(G,v)：若图G中存在顶点v，则返回顶点v在图中的位置。

● 获取顶点的值-GetVextex(G,v)：若图G中存在某顶点v，则返回该顶点存储的数据元素。

● 设置顶点的值-SetVextex(G,v,value)：若图中存在某顶点，则将该顶点的值设置为给定值。

● 求邻接点-GetFirAdVex(G,*v)：返回该顶点的第一个邻接点，若该顶点不存在邻接点则返回空。

● 求下一个邻接点-GetNextAdVex(G,v,*w)：返回顶点v相对于顶点w的下一个邻接点，若w是最后一个邻接点，则返回空。

● 插入顶点-InsertVextex(*G,v)：在图G中插入新顶点v。

● 删除顶点-DeleteVextex(*G,v)：删除图G中的顶点v以及相关的弧。

● 添加边-InsertEdge(*G,v,w)：在图G中添加边<v,w>，若图G是无向图，还需添加其对称边<w,v>。

● 删除边-DeleteEdge(*G,v,w)：在图G中删除边<v,w>，若图G是无向图，还需删除其对称边<v,w>。

以上是基于图本身的常用操作，其中的(3)-(7)使用比较频繁，(8)-(11)涉及对图的修改，一般不用。