【导读】2016秋季龙岩市武平县事业单位考试：计算机之数据结构与算法之图的遍历福建事业单位微信公众号(fjsyzk),福建事业单位培训咨询电话：0591-87896332,微信咨询请扫描下方二维码：
图的遍历
图的遍历和树的遍历类似，希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫图的遍历。
对于图的遍历来说，如何避免因回路陷入死循环，就需要科学地设计遍历方案，通过有两种遍历次序方案：深度优先遍历和广度优先遍历。
2.1 深度优先遍历
深度优先遍历，也有称为深度优先搜索，简称DFS。其实，就像是一棵树的前序遍历。
它从图中某个结点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中的所有顶点都被访问到为止。
我们用邻接矩阵的方式，则代码如下所示。
如果使用的是邻接表存储结构，其DFSTraverse函数的代码几乎是相同的，只是在递归函数中因为将数组换成了链表而有不同，代码如下。
对比两个不同的存储结构的深度优先遍历算法，对于n个顶点e条边的图来说，邻接矩阵由于是二维数组，要查找某个顶点的邻接点需要访问矩阵中的所有元素，因为需要O(n2)的时间。而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，所以是O(n+e)。显然对于点多边少的稀疏图来说，邻接表结构使得算法在时间效率上大大提高。
——推荐阅读——
招聘公告--2024年福建事业单位招聘考试日历 | 职位表查询
考试报名--2024年福建事业单位招聘报名入口 | 报名问题咨询
备考指导--历年福建事业单位进面分数线 | 每日刷题练习 | 模考练习
课程推荐--2024年福建事业单位图书教材 | 网课推荐 | 面授课程
（编辑：admin）
公告什么时候出？
报考条件是否符合？
公考小白怎么备考?
冲刺资料怎么领取？
(1).png)
700w+
阅读量100w+
粉丝300w+
点赞数
福建华图微信
福州市鼓楼区五四路82号融都国际大厦9层
客服热线：0591-87896332
网站：https://fuzhou.huatu.com
