图的基本操作

一、图解操作

明白原理即可；

1、操作一：判断图G中是否存在从顶点v到w的边

1、无向图的情况

如下图所示，中间为邻接矩阵，右侧为邻接表，分别用这两种方法来存储无向图；

问题1：那么，我们如何判断是否存在边(C,D)呢？

1、在邻接矩阵中，可以通过查看C行D列的值是否为1，或者是通过查看D行C列的值是否为1，如果为1，则存在边(C,D);
2、在邻接表中，可以通过遍历C的边链表，看是否存在D的下标，或者是遍历D的边链表，看是够存在C的下标；

问题2：两种操作方法的时间复杂度为多少？
1、在邻接矩阵中，可以通过下标直接定位元素，查看其值是否为1，所以时间复杂度为O(1);
2、在邻接表中，最好的情况是，待查询的边不存在，或者待查询的边的顶点在边链表的第一个位置，这种情况时间复杂度为O(1);
最坏的情况是，待查询的边的顶点和每个顶点都有边，且待查询的边的顶点在边链表的最后一个位置，即n-1个位置，那么时间复杂度为O(n-1),即O(n);

2、有向图的情况

如下图所示，中间为邻接矩阵，右侧为邻接表，分别用这两种方法来存储有向图；

问题1：那么，我们如何判断是否存在边(C,D)呢？

1、在邻接矩阵中，可以通过查看C行D列的值是否为1，如果为1，则存在边<C,D>;不可以是通过查看D行C列的值是否为1，如果为1，则存在边<D,C>;

2、在邻接表中，可以通过遍历C的边链表，看是否存在D的下标，如果存在，则存在边<C,D>
不可以是遍历D的边链表，看是够存在C的下标，如果存在，则存在边<D,C>；

问题2：两种操作方法的时间复杂度为多少？
与无向图一致；

2、操作二：列出图G中与顶点v邻接的边

1、无向图的情况

如下图所示，中间为邻接矩阵，右侧为邻接表，分别用这两种方法来存储无向图；

问题1：那么，我们如何判断与顶点C邻接的边呢？
1、在邻接矩阵中，判断C行的每一列是否存在为1的值，如果为1，则为邻接边；
2、在邻接表中，通过遍历C的边链表，边链表中存在的下标则为邻接表；

问题2：两种操作方法的时间复杂度为多少？
1、在邻接矩阵中，需要判断一行，所以时间复杂度为O(n);
2、在邻接表中，最好的情况为O(1),最坏的情况为O(n-1);

2、有向图的情况

如下图所示，中间为邻接矩阵，右侧为邻接表，分别用这两种方法来存储有向图；

在有向图中，与顶点邻接的边存在出边或者入边；
什么是出边，边<C,D>则为C的出边；
什么是入边，边<D,C>则为C的入边；

问题1：那么，我们如何判断与顶点C邻接的边呢？
1、在邻接矩阵中，出边通过遍历C行的每一列，如果存在值为1，则说明存在以C为起点的出边；入边通过编历C列的每一行，如果存在值为1，则说明存在以C为终点的入边；
2、在邻接表中，出边通过遍历C的边链表，如果存在结点，则说明存在以C为起点的出边；入边则需要遍历整个邻接表的边链表，看边链表节点中是否存在等于节点C下标的下标，若存在，则说明存在以C为终点的入边。

问题2：两种操作方法的时间复杂度为多少？
1、在邻接矩阵中，需要扫描一行和一列，时间复杂度为O(n)
2、在邻接表中，出边最好情况为O(1),最坏情况为(n); 找入边，需要扫描全部的边链表的结点，时间复杂度为O(E)，取复杂度 O( max(|n|,|E|) );

3、操作三：在图中插入顶点V

在图中插入一个顶点，它与图中的顶点无边，所以只需要在数组的空白个位置加入元素即可；
实现如下：
空白位置为:vexnum;
所以只需要G.vex[G.vexnum]=新顶点 即可；
G.vexnum++;

4、操作四：从图中删除顶点V

假设删除顶点C，删除顶点C，
在邻接矩阵中，需要将C列后的每一列向前移动，然后将C行后的每一行向上移动；
在邻接表总，需要将C顶点删除，然后其边链表也删除，将别的顶点中存在C结点的结点删除；

5、操作5：在图G中插入一条顶点V到W的边

1、无向图情况

假设插入一条边(B,D);
在邻接矩阵中，B行D列置为1，D行B列也置为1；时间复杂度为O(1)
在邻接表中，在B和D的边链表中增加一个结点，可以将结点插在边链表头部，这样时间复杂度业务O(1);

2、有向图情况

假设插入一条边<B,D>;
在邻接矩阵中，B行D列置为1即可，时间复杂度为O(1)
在邻接表中，在B和边链表中增加一个结点，可以将结点插在边链表头部，这样时间复杂度业务O(1);

6、重要操作

操作FirstAdjVex(G,v):
假设求E的邻接顶点，
在邻接矩阵中吗，扫描E行，找到第一个为1的值即可，如图所示，第一个邻接顶点为C，不存在返回-1；
在邻接表中，扫描顶点E的边链表，获取其第一个结点即可，不存咋返回-1；

操作NextAdjvex(G,v,w);
假设NextAdjVex(G,0,1)：含义就是在图G中，查看顶点A相对于B的下一个邻接点，为C；
假设NextAdjVex(G,0,2)：含义就是在图G中，查看顶点A相对于C的下一个邻接点，为D；
假设NextAdjVex(G,0,3)：含义就是在图G中，查看顶点A相对于D的下一个邻接点，为-1；

在图的算法中经常会使用到这2个函数；
通过下面操作，可以得到某个顶点v全部的邻接点；