北京事业单位考试

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

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

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

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

  二、图的遍历

  图的遍历和树的遍历类似,希望从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次,这一过程就叫图的遍历。

  对于图的遍历来说,如何避免因回路陷入死循环,就需要科学地设计遍历方案,通过有两种遍历次序方案:深度优先遍历和广度优先遍历。

  2.1 深度优先遍历

  深度优先遍历,也有称为深度优先搜索,简称DFS。其实,就像是一棵树的前序遍历。

  它从图中某个结点v出发,访问此顶点,然后从v的未被访问的邻接点出发深度优先遍历图,直至图中所有和v有路径相通的顶点都被访问到。若图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中的所有顶点都被访问到为止。

  我们用邻接矩阵的方式,则代码如下所示。

  如果使用的是邻接表存储结构,其DFSTraverse函数的代码几乎是相同的,只是在递归函数中因为将数组换成了链表而有不同,代码如下。

  对比两个不同的存储结构的深度优先遍历算法,对于n个顶点e条边的图来说,邻接矩阵由于是二维数组,要查找某个顶点的邻接点需要访问矩阵中的所有元素,因为需要O(n2)的时间。而邻接表做存储结构时,找邻接点所需的时间取决于顶点和边的数量,所以是O(n+e)。显然对于点多边少的稀疏图来说,邻接表结构使得算法在时间效率上大大提高。

  2.2 广度优先遍历

  广度优先遍历,又称为广度优先搜索,简称BFS。图的广度优先遍历就类似于树的层序遍历了。

  邻接矩阵做存储结构时,广度优先搜索的代码如下。

  对于邻接表的广度优先遍历,代码与邻接矩阵差异不大, 代码如下。

  对比图的深度优先遍历与广度优先遍历算法,会发现,它们在时间复杂度上是一样的,不同之处仅仅在于对顶点的访问顺序不同。可见两者在全图遍历上是没有优劣之分的,只是不同的情况选择不同的算法。

(编辑:刘冉)
北京华图: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