数据结构之图的基本操作

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

1.1 如何判断无向图是否存在边 (C, D) ?

图G

1.1.1 邻接矩阵法判断

邻接矩阵法

邻接矩阵表示法可以根据顶点C和D确认边在数组中的位置G(2,3)位置上存储的数字为1（如上图红色虚线框所示，也可以取G(3,2)位置上存储的数字），所以确定边 (C, D) 存在

1.1.2 邻接表法

邻接表法

邻接表法需要遍历C顶点的所有链表（如上图红色虚线框所示，也可以遍历D顶点的所有链表找出是否有C的边表），找出是否有顶点D的边表，从图中可知遍历到第二个节点时就可以确认存在边 (C, D)

对比两种方式，我们发现邻接矩阵法只需要判断一个值，比邻接表法更高效

1.2 如何判断有向图是否存在边 <C, D> ？

1.2.1 邻接矩阵法判断

邻接矩阵法

邻接矩阵表示法可以根据顶点C和D确认边在数组中的位置G(2,3)位置上存储的数字为1（如上图红色虚线框所示），所以确定边 <C, D> 存在

1.2.2 邻接表法判断

邻接表法

邻接表法需要遍历C顶点的所有链表（如上图红色虚线框所示），找出是否有顶点D的边表，从图中可知遍历到第二个节点时就可以确认存在边 <C, D>

对比两种方式，我们发现邻接矩阵法判断有向图同样只需要判断一个值，比邻接表法更高效

二、列出图G中与结点X邻接的边

2.1 如何判断无向图G中与结点B邻接的边

2.1.1 邻接矩阵法判断

邻接矩阵法

邻接矩阵表示法可以遍历顶点B所在的行的所有数字为1的数量来确定与结点B邻接的边（如上图红色虚线框所示），所以确定邻接的边有两条 (A,B) 和 (B,C)

2.1.2 邻接表法

邻接表法

邻接表法只需要遍历顶点B的所有链表即可确定邻接的边有两条 (A,B) 和 (B,C)

对比两种方式，我们发现邻接表法只需要遍历链表即可，比邻接矩阵法更高效

2.2 如何判断有向图G中与结点B邻接的边

2.2.1 邻接矩阵法判断

邻接矩阵法

邻接矩阵表示法可以遍历顶点B所在的行的数字为1的数量来确定出度，所在列的数字为1的数量来确定入度，入度加出度即为结点B邻接的边，所以确定邻接的边有两条 <B,A> 和 <B,C>

2.2.2 邻接表法

邻接表法

邻接表法则需要遍历所有顶点的所有链表才可以确定邻接的边有两条<B,A> 和 <B,C>

对比两种方式，我们发现邻接矩阵法只需要遍历与结点B相关的数据，比邻接表法更高效

三、在图G中插入顶点F

3.1 邻接矩阵法

邻接矩阵法

邻接矩阵法结点数组尾部新增一个结点，二维数组新增行尾新增一行默认值全为0，列尾新增一列默认值全为0即可

3.2 邻接表法

邻接表法

邻接表法顶点数组尾部新增一个结点，链表为空即可

四、从图G中删除顶点A

4.1 邻接矩阵法

邻接矩阵法

邻接矩阵法将结点数组A的位置置空，边表A所在的行和列数据全部置空即可

4.2 邻接表法

邻接表法

邻接表法将结点数组A的引用置空即可

五、若无向边 (A,D) 或者邮箱边 <A,D> 不存在，则向图G中添加该边

5.1 邻接矩阵法

邻接矩阵法

邻接矩阵法无向图需要把 G(0,3) 和 G(3,0) 的值修改为1即可
邻接矩阵法无向图需要把 G(0,3)的值修改为1即可

5.2 邻接表法

邻接表法

邻接表法无向图需要把顶点A和顶点D的边链表分别增加一个边结点即可
邻接表法有向图需要把A的边链表增加一个边结点即可

六、若无向边 (B,C) 或者有向边 <B,C> 存在，则在图G中删除该边

6.1 邻接矩阵法

邻接矩阵法

邻接矩阵法无向图需要把 G(1,2) 和 G(2,1) 的值修改为0即可
邻接矩阵法有向图需要把 G(1,2) 的值修改为0即可

6.2 邻接表法

邻接表法

邻接表法无向图需要把结点B的边链表中的2边删除，结点C的遍链表中的1边删除即可
邻接表法邮箱边需要吧结点B的边链表中的2边删除接口

七、邻接点操作

邻接点操作

八、权值操作

权值操作