C++实现图的邻接表存储结构及其简析
对于图来说，邻接矩阵是不错的一种图存储结构，但是我们也发现，对于边数相对顶点较少的图，这种结构是存在对存储空间的极大浪费的。因此我们考虑另外一种存储结构方式：邻接表（Adjacency List），即数组与链表相结合的存储方法。
邻接表的处理方法是这样的：
1、图中顶点用一个一维数组存储，另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。
2、图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点vi的边表，有向图称为顶点vi作为弧尾的出边表。
邻接表中的头结点以及表节点结构如下：
图1
无向图的邻接表：
图2
有向图的邻接表：
图3
邻接表相关知识点：
（1）设图中有n个顶点，e条边，则用邻接表表示无向图时，需要n个顶点结点，2e个表结点【上图2所示】；用邻接表表示有向图时，若不考虑逆邻接表，只需n个顶点结点，e个边结点【上图3所示】。
（2）在无向图的邻接表中，顶点vi的度恰为第i个链表中的结点数。
（3）在有向图中，第i个链表中的结点个数只是顶点vi的出度。
建立邻接表的时间复杂度：
以下截图的代码与后续提供的源码截图不一样，这里只是为了说明建立邻接表所需要执行的程序步骤：
图4
从截图上看程序执行步数的多少最终决定于两个for循环语句。刻意观察到第一个for循环语句所需执行步数为2*G.numvertex，第二个for循环语句所需执行步数为11*G.numarc。两者之和为2*G.numvertex+11*G.numarc【其中G.numvertex为顶点数，G.numarc为边数，我们分别记为n和e】。当顶点数以及边数足够大时，系数可以忽略，因此我们就可以把代表程序总执行步数的记为O(n+e)。
C++源码截图如下：
代码功能【实现了以顶点顺序表、边链表为存储结构的邻接表；实现了图的创建（有向/无向/图）、边的增删操作、】
图5
图6
参考
1、《算法导论》
