第五章:图(图的基本操作)
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都代表某一个边的存在
- 邻接表:遍历对于顶点的边表,所有边表结点都代表一个邻接的边