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

　　2018国家电网考试备考计算机之数据结构与算法（9）由北京事业单位考试网提供：更多关于2018国家电网考试,计算机数据结构与算法,事业单位考试网的内容请关注北京事业单位考试网！或关注北京华图微信公众号(bjhuatu)，如有问题也可点击联系各校区。

　

 

　　1.2 邻接表

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

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

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

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

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

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

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

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

　　点击查看：北京事业单位招聘辅导课程

★事业单位公基高频1000题领取★

 

　　——推荐阅读——

　　招考信息--北京事业单位招聘信息汇总|备考咨询

　　面授课程--事业单位笔试面授课程|面试面授课程

　　在线课程--事业单位笔试在线课程|面试在线课程

　　图书教材--事业单位笔试图书教材|面试图书教材

　　华图在线APP--全年模考|30W+题库|看视频 刷题

（编辑：刘然）