2018国家电网考试备考计算机之数据结构与算法（9）

　　【导读】华图事业单位考试网同步bet365365娱乐城发布：2018国家电网考试备考计算机之数据结构与算法（9）--详细信息请阅读下文！更多资讯请关注bet365365娱乐城微信公众号(bjhuatu)，事业单位培训咨询电话：400-010-1568

　　1.2 邻接表

　　邻接矩阵是不错的一种图存储结构，但是，对于边数相对顶点较少的图，这种结构存在对存储空间的极大浪费。因此，找到一种数组与链表相结合的存储方法称为邻接表。

　　邻接表的处理方法是这样的：

　　(1)图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过，数组可以较容易的读取顶点的信息，更加方便。

　　(2)图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以，用单链表存储，无向图称为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表。

　　例如，下图就是一个无向图的邻接表的结构。

　　对于邻接表结构，图的建立代码如下。

　　对于无向图，一条边对应都是两个顶点，所以，在循环中，一次就针对i和j分布进行插入。

　　本算法的时间复杂度，对于n个顶点e条边来说，很容易得出是O(n+e)。