前端面试100问(5)
2023-09-11 14:18:53 时间
码字不易,有帮助的同学希望能关注一下我的微信公众号:Code程序人生,感谢!代码自用自取。
题目:
介绍下深度优先遍历和广度优先遍历,如何实现?
第五题问的是深度优先遍历和广度优先遍历,我是从dom节点的遍历来理解这个问题的
深度优先遍历
深度优先遍历DFS 与树的先序遍历比较类似。
假设初始状态是图中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和v有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到,则另选一个未被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。
/*深度优先遍历三种方式*/
let deepTraversal1 = (node, nodeList = []) => {
if (node !== null) {
nodeList.push(node)
let children = node.children
for (let i = 0; i < children.length; i++) {
deepTraversal1(children[i], nodeList)
}
}
return nodeList
}
let deepTraversal2 = (node) => {
let nodes = []
if (node !== null) {
nodes.push(node)
let children = node.children
for (let i = 0; i < children.length; i++) {
nodes = nodes.concat(deepTraversal2(children[i]))
}
}
return nodes
}
// 非递归
let deepTraversal3 = (node) => {
let stack = []
let nodes = []
if (node) {
// 推入当前处理的node
stack.push(node)
while (stack.length) {
let item = stack.pop()
let children = item.children
nodes.push(item)
// node = [] stack = [parent]
// node = [parent] stack = [child3,child2,child1]
// node = [parent, child1] stack = [child3,child2,child1-2,child1-1]
// node = [parent, child1-1] stack = [child3,child2,child1-2]
for (let i = children.length - 1; i >= 0; i--) {
stack.push(children[i])
}
}
}
return nodes
}
广度优先遍历
广度优先遍历 BFS
从图中某顶点v出发,在访问了v之后依次访问v的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问,直至图中所有已被访问的顶点的邻接点都被访问到。 如果此时图中尚有顶点未被访问,则需要另选一个未曾被访问过的顶点作为新的起始点,重复上述过程,直至图中所有顶点都被访问到为止。
let widthTraversal2 = (node) => {
let nodes = []
let stack = []
if (node) {
stack.push(node)
while (stack.length) {
let item = stack.shift()
let children = item.children
nodes.push(item)
// 队列,先进先出
// nodes = [] stack = [parent]
// nodes = [parent] stack = [child1,child2,child3]
// nodes = [parent, child1] stack = [child2,child3,child1-1,child1-2]
// nodes = [parent,child1,child2]
for (let i = 0; i < children.length; i++) {
stack.push(children[i])
}
}
}
return nodes
}
更多关于前端的面试题内容关注我的公众号:Code程序人生。
有微信小程序课设、毕设需求联系个人QQ:505417246
关注下面微信公众号,可以领取微信小程序、Vue、TypeScript、前端、uni-app、全栈、Nodejs、Python等实战学习资料
最新最全的前端知识总结和项目源码都会第一时间发布到微信公众号,请大家多多关注,谢谢
相关文章
- 大前端的自动化工厂(2)—— SB Family
- 优志愿前端数据加密破解-python
- EasyDSS高性能RTMP、HLS(m3u8)、HTTP-FLV、RTSP流媒体服务器web前端:vue组件之间的传值,父组件向子组件传值
- EasyNVR H5无插件摄像机直播解决方案前端解析之:监控实时直播的四分屏的前端展示
- 高性能流媒体服务器EasyDSS前端重构(三)- webpack + vue + AdminLTE 多页面引入 element-ui
- 前端学习 -- Xhtml语法规范
- 前端面试
- Web前端面试真题(算法篇):005篇
- 前端面试及答案:css 选择器有哪些?权重是什么样的?
- 前端基础面试:前端页面由哪三层构成,分别是什么,作用是什么?
- Android 开发如何进阶:跳出舒适区,提升技术深度与广度,走在行业前端
- 移动前端UI选择
- 想要前端面试顺利拿offer,这篇文章要看仔细~
- 网友:想转行IT行业是学习软件测试好,还是前端编程?
- 【前端领域高频笔试面试】—— Html5+CSS3相关
- 20212022最新Web前端经典面试试题及答案-史上最全前端面试题(含答案)、前端面试题大全、前端进阶必知必会知识点
- 前端面试之 语录: