💼【每日一题】(56题)介绍下深度优先遍历和广度优先遍历，如何实现？

一、前言

每日一题这不仅仅是一份用于求职面试的攻略，也是一份前端er用来检视自己。

学习算法目的：

•技术进阶，提升自身代码编程能力和逻辑能力，锻炼思维增加编写代码都思路。•为面试做准备，不少大厂面试都会考察算法和数据结构，为了进入心仪都公司，学习数据结构与算法是不会错的。

歪个楼：

2021春招开始了

校招内推码：8J5ZSB8

校招流程：https://jobs.bytedance.com/campus/invite?referral_code=8J5ZSB8

内推字节跳动：

二、两种遍历算法：

•深度优先遍历•广度优先遍历

1、深度优先遍历（DFS）

深度优先遍历（Depth-First-Search），是搜索算法的一种，它沿着树的深度遍历树的节点，尽可能深地搜索树的分支。当节点v的所有边都已被探寻过，将回溯到发现节点v的那条边的起始节点。

这一过程一直进行到已探寻源节点到其他所有节点为止，如果还有未被发现的节点，则选择其中一个未被发现的节点为源节点并重复以上操作，直到所有节点都被探寻完成。

简单的说，DFS就是从图中的一个节点开始追溯，直到最后一个节点，然后回溯，继续追溯下一条路径，直到到达所有的节点，如此往复，直到没有路径为止。

DFS 可以产生相应图的拓扑排序表，利用拓扑排序表可以解决很多问题，例如最大路径问题。一般用堆数据结构来辅助实现DFS算法。

注意：深度DFS属于盲目搜索，无法保证搜索到的路径为最短路径，也不是在搜索特定的路径，而是通过搜索来查看图中有哪些路径可以选择。

步骤：

访问顶点v

依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问

若此时途中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到所有顶点均被访问过为止

实现：

Graph.prototype.dfs = function() { var marked = [] for (var i=0; i<this.vertices.length; i++) { if (!marked[this.vertices[i]]) { dfsVisit(this.vertices[i]) } } function dfsVisit(u) { let edges = this.edges marked[u] = true console.log(u) var neighbors = edges.get(u) for (var i=0; i<neighbors.length; i++) { var w = neighbors[i] if (!marked[w]) { dfsVisit(w) } } }}

测试：

graph.dfs()// 1// 4// 3// 2// 5

测试成功

2、广度优先遍历（BFS）

广度优先遍历（Breadth-First-Search）是从根节点开始，沿着图的宽度遍历节点，如果所有节点均被访问过，则算法终止，BFS 同样属于盲目搜索，一般用队列数据结构来辅助实现BFS

BFS从一个节点开始，尝试访问尽可能靠近它的目标节点。本质上这种遍历在图上是逐层移动的，首先检查最靠近第一个节点的层，再逐渐向下移动到离起始节点最远的层

步骤：

创建一个队列，并将开始节点放入队列中

若队列非空，则从队列中取出第一个节点，并检测它是否为目标节点

若是目标节点，则结束搜寻，并返回结果

若不是，则将它所有没有被检测过的字节点都加入队列中

若队列为空，表示图中并没有目标节点，则结束遍历

实现：

Graph.prototype.bfs = function(v) { var queue = [], marked = [] marked[v] = true queue.push(v) // 添加到队尾 while(queue.length > 0) { var s = queue.shift() // 从队首移除 if (this.edges.has(s)) { console.log('visited vertex: ', s) } let neighbors = this.edges.get(s) for(let i=0;i<neighbors.length;i++) { var w = neighbors[i] if (!marked[w]) { marked[w] = true queue.push(w) } } }}

测试：

graph.bfs(1)// visited vertex: 1// visited vertex: 4// visited vertex: 3// visited vertex: 2// visited vertex: 5

更多阅读

••••••

往期「每日一题」

1、JavaScript && ES6

•第 47 题：•第 46 题：•第 41 题：•第 40 题：•第 39 题：•第 30 题：•第 28 题：•第 22 题：•第 21 题：•第 20 题：•第 19 题：•第 18 题：•第 17 题：•第 16 题：•第 15 题：•第 14 题：•第 13 题•第 12 题•第 11 题•第 10 题•第 8 题•第 7 题•第 6 题•第 3 道•第 2 道

2、浏览器

•第 9 题

3、Vue

•第 5 道

4、React

•第 38 道

5、HTML5

•第 29 道

6、算法

•第 54 题•第 53 题•第 52 道•第 51 道[•第 50 道•第 49 道•第 48 道•第 45 道•第 44 道•第 37 道•第 36 道•第 35 道•第 34 道•第 33 道•第 32 道•第 31 道[•第 27 道•第 26 道•第 25 道•第 24 道•第 4 道

7、Node

•第 23 道

8、Http

•第 1 道•第 42 题•第 43 题 

9、年终总结

•

谢谢支持

1、文章喜欢的话可以「分享，点赞，在看」三连哦。

3、长按下面图片，关注「松宝写代码」，是获取开发知识体系构建，精选文章，项目实战，实验室，每日一道面试题，进阶学习，思考职业发展，涉及到JavaScript，Node，Vue，React，浏览器，http，算法，端相关，小程序等领域，希望可以帮助到你，我们一起成长～