学习数据结构--第五章：图（图的基本操作）

第五章：图（图的基本操作）

1.Adjacent(G,x,y)

Adjacent(G,x,y) 判断图G是否存在边<x,y>或(x,y)

如上 无向图 的邻接矩阵和邻接表表示方法，判断方法分别为：

• 邻接矩阵：判断该边是否存在直接判断对应邻接矩阵中的值即可，如果是1存在否则不存在
• 邻接表：判断对应顶点的边表是否存在这样一条边的边表结点

因为无向图的邻接矩阵和邻接表我们会存储两遍，所以无论第一个结点x做行号，还是y做行号都可以进行查找

如上 有向图 的邻接矩阵和邻接表表示方法，判断方法分别为：

• 邻接矩阵：判断该边是否存在直接判断对应A[x][y]邻接矩阵中的值即可，如果是1存在否则不存在
• 邻接表：判断第一个端点x对应的顶点的边表是否存在这样一条边的表结点

因为是有向图所以每个对于邻接矩阵和邻接表都只会存储一此，所以传入的参数第一个x为边的起点的下标

2.Neighbors(G,x)

Neighbors(G,x)列出图G中与结点x(顶点)邻接的边

如上 无向图 列出对应结点邻接边

• 邻接矩阵：直接搜索邻接矩阵中该顶点的 行或列 中值为1的，值为1都代表某一个边的存在
• 邻接表：遍历对于顶点的边表，所有边表结点都代表一个邻接的边

如上 有向图 列出对应结点邻接边

• 邻接矩阵：我们需要遍历该顶点对应的 行和列 中值为1的，值为1都代表某一个边的存在（行代表出边，列代表入边）
• 邻接表：首先遍历对应顶点的边表，找到所有的以该顶点为头节点的边（出边），然后遍历整个邻接表找到以该顶点为尾结点的边（入边）

3.InsertVertex(G,x)

InsertVertex(G,x) 在图G中插入顶点x

其实关于插入顶点有向图和无向图差不多，这里我们要插入一个顶点F

无向图：首先我们需要将顶点F插入到顶点表中，顶点表是一个数组无法扩充所以我们需要新建立一个数组把之前的顶点插入进来，然后加上顶点F，接着我们需要修改邻接矩阵，我们依旧需要扩充二维数组(同样创建一个二维数组把旧的值和新的值都添加进去)。这里只是插入一个顶点，并未确定连接关系

有向图：同样我们新建立一个顶点表，将旧值和新值都添加进去，边表置为空即可

4.DeleteVertex(G,x)

DeleteVertex(G,x)从图G中删除顶点x

删除一个顶点还需要删除与该顶点有关所有的边

• 邻接矩阵：将顶点表对应的结点的值设为空，矩阵二维数组该顶点对应的行和列设为空，所以我们有时也可以采用缩小数组来删除结点。
• 邻接表：我们需要删除顶点表对应的顶点，接着清空该顶点表对应的边表

5.AddEdge(G,x,y)

AddEdge(G,x,y)若无向边(x,y)或者有向边<x,y>不存在，则向图G中添加该边

如上无向图 添加一条边

• 邻接矩阵：添加一条边，我们需要修改该边在矩阵中的值为1，例如增加AD边，我们需要修改A[0][3]=1和A[3][0]=1
• 邻接表：添加一条边，我们需要在两个顶点对应的边表中分别增加彼此结点

6.RemoveEdge(G,x,y)

RemoveEdge(G,x,y) 若无向边(x,y)或者有向边<x,y>存在，则在图G中删除该边

如上无向图 删除一条边

• 邻接矩阵：删除一条边，则需要修改该边对应的值为0，例如删除BC边，我们需要修改A[1][2]=0和A[2][1]=0
• 邻接表：删除一条边，则需要删除两个顶点对应边表中的彼此结点

7.XxxxNeighbor(G,x)

FirstNeighbor(G,x) 求图G中顶点x的第一个邻接点，若有则返回顶点号。若没有邻接点或者图不存在x，则返回-1

NextNeighbor(G,x) 假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1

例如我们找B顶点的

• FirstNeighbor(G,x)第一个邻接点
• • 邻接矩阵：我们按照邻接矩阵顺序查找，搜索B对应的行，我们发现这一行第一个值不为1的点为它的第一个邻接点为A（即对应列号较小且值为1的结点）
  • 邻接表：遍历对应顶点的边表，第一个结点即为它的第一个邻接点
• NextNeighbor(G,x) 下一个邻接点
• • 邻接矩阵：同理我们按照上面的规律继续往后查找，找到下一个值为1的即为它的下一个邻接点
  • 邻接表：遍历对应顶点的边表，第一个结点的下一个结点即为它的下一个邻接点

8.Xxx_edge_value(G,x,y)

我们知道当边有权值时的图我们叫做网，对于网我们有获取和设置该边权值的操作

Get_edge_value(G,x,y) 获取图G中边(x,y)或<x,y>对应的权值 v

Set_edge_value(G,x,y) 设置图G中边(x,y)或<x,y>对应的权值 v

• 获取边的权值
• • 邻接矩阵：直接找到该边对应的二维数组的值即为该边的权重
  • 邻接表：遍历邻接矩阵找到对应结点的存储的权重
• 设置边的权值
• • 邻接表矩阵：同理
  • 邻接表：同理

7.理木客

数据结构相关知识，公众号理木客同步更新中，欢迎关注