福建事业单位考试

面授课程网校课程图书教材|

砖题库直播职位库文库题库阅读|

微博微信QQ群问答师资

0591-87618197
您当前位置:公务员考试网 > 福建公务员考试网 > 福建事业单位考试 > 备考技巧 > 专业课 > 2016秋季龙岩市武平县事业单位考试:计算机之数据结

2016秋季龙岩市武平县事业单位考试:计算机之数据结构与算法之图的遍

2016-07-07 22:46 事业单位考试 http://fj.huatu.com/sydw 作者:福建华图 来源:福建省公务员考试网

【导读】2016秋季龙岩市武平县事业单位考试:计算机之数据结构与算法之图的遍历

课程推荐:福建省事业单位笔试课程 福建省事业单位面试课程

课程咨询:范老师(微信fjhtfls) 王老师(微信fjhtwls) 张老师(扣扣2625006339)

 图的遍历

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

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

  2.1 深度优先遍历

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

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

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

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

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

福建事业单位考试招考信息/福建事业单位面试公告

福建事业单位考试报名指南/福建事业单位考试报考指导

福建事业单位考试笔试真题/福建事业单位面试真题

福建事业单位考试备考资料/福建事业单位面试备考

福建事业单位考试行测备考资料/福建事业单位考试公共基础知识备考资料

(编辑:福建华图003)

华图在线APP客户端下载

2016年福建省公务员面试课程
京ICP备11028696号 京ICP证090387号