北京事业单位考试

您当前位置:公务员考试网 > 北京人事考试网 > 北京事业单位考试 > 备考资料 > 2018国家电网考试备考计算机之数据结构与算法(9)

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

2018-03-09 14:09:18 事业单位考试网 http://bj.huatu.com/sydw/ 文章来源:北京华图

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

  1.2 邻接表

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

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

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

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

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

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

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

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

(编辑:刘冉)
北京华图:bjhuatu
想考上公务员的人都关注了我们!
立即关注

10万+
阅读量
10w+
粉丝
10000+
点赞数

联系我们
微信二维码

北京华图教育官方微信

北京华图

北京市海淀区花园路7号新时代一层

北京华图宏阳教育文化发展股份有限公司分公司

客服热线:400-010-1568

网站:http://bj.huatu.com

  • 牡丹园校区
  • 西城校区
  • 朝阳校区
  • 顺义校区
  • 大兴校区
  • 昌平校区
  • 平谷校区
  • 房山校区

海淀区花园路7号新时代大厦一层

客服热线:400-010-1568

网站:http://bj.huatu.com

西城区阜成门万通新世界A座1211

客服热线:010-58463857

网站:http://bj.huatu.com

朝阳区定福庄北里一号院鲁班大厦809室

客服热线:010-59453600/57237009

网站:http://bj.huatu.com

顺义双兴北区10号楼底商(北城根路与光明北街交叉路口)

客服热线:010-57282681

网站:http://bj.huatu.com

大兴区金星西路绿地中央广场B座609室

客服热线:010-58463856

网站:http://bj.huatu.com

昌平区政府街4-3号特步专卖店二楼(昌平二中斜对面)

客服热线:010-57282680

网站:http://bj.huatu.com

平谷区建设街229号二层(平谷六中北路口往西50米)

客服热线:010-59146957

网站:http://bj.huatu.com

房山区良乡拱辰南大街荣鹏花园底商

客服热线:010-57428000

网站:http://bj.huatu.com