6.2.2邻接表法-图的存储

知识总览：

为什么要用邻接表

因为邻接矩阵的空间复杂度高(O(n²))，且不适合边少的稀疏图，所以有了邻接表 

用代码表示顶点、图

声明顶点+图信息

声明顶点用一维数组存储各个顶点的信息，一维数组字段包括2个，每个顶点的数据域信息和指向该顶点的第一条边或弧的信息，声明图：一维数组+该图目前有多少顶点vexnum+改图目前有多少边arcnum

无向图邻接表：

如下图中的data字段上的0、1、2、3、4、5是一维数组的索引，每个data字段都有一个first指针，为指向该顶点的第一条边的指针，虽然指针就一个，但是指向的节点可能有多个，就看这个节点和其他节点有几条边，first指针指向该节点指向的下一个节点信息，节点信息包括该条边指向的节点，如A和B、A和C、A和D都相邻，都有边，都有路径，那first指针指向的节点信息中的是B、C、D，这些节点信息都在一维数组中，每个节点信息都有编号，于是first指针就指向了编号，如B的编号为1，C的编号是2，D的编号是3，所以指向第一条边那依次指向1、2、3（3,2,1的位置也可互换，即邻接表的表示方式不唯一 ，但是邻接矩阵的表示方式唯一），即有一条A指向B或者说指向1的边，A指向C或者说指向2的边，A指向D或者说指向3的边。如果是带权图，还可以在边指向的节点信息中加上权值信息InfoType type字段

因为是无向图，一条边就要在2个节点VNode的first指针存储2个边节点信息。A指向B就意味着B指向A，所以A节点中first指针B，B节点first指针要指向A节点，但是是同一个边，即1个边对应了2个节点，所以有边节点的数量是2|E|即边节点=2倍边的数量

无向图中空间复杂度=顶点的占用空间+2倍边的空间=O(|v|+2|E|)（应该是就存储顶点信息+first指针吧，first指针又存储了边节点，边节点又和边的数量有关系，所以实际是存储的边节点信息。。。）

无向图的度=该节点下first指针中边节点的个数（度是针对节点来说的）

有向图邻接表：

有向图中一条边只会在一个VNode节点信息上指向边节点，即A指向B这条边，只会在A节点的first指针上指向边节点B，不会在B节点的first指针指向A，即边的数量=指向边节点的数量

有向图空间复杂度=顶点的占用空间+边的空间=O(|v|+|E|)

有向图的度=入度+出度（度是针对节点来说的）

有向图的出度=每个节点的first指针指向的边节点的个数(因为first指针指向的是从该节点指向的其他节点)

有向图的入度=遍历所有的节点信息，看看哪个节点上的first指针下有该节点的和(如A节点的入度就是遍历所有的节点，看看哪个节点的first指针下有边节点A，有A的数量之和即为入度)，因为求入度要遍历所有节点，所以时间开销大

知识回顾

未完待续。。。。。。。