web前端|js教程
算法,javascript
web前端-js教程
安卓购物车源码,vscode修改文件,ubuntu系统下格式化u盘,tomcat 删除工程,增删改查sqlite,jquery手机端轮播图插件,ssm框架接受前端数据,爬虫慕课视频下载,迅雷种子php,seo人员分配,帝国cms 网站转移,网页页面模板,网页包装模板lzw
本篇文章给大家带来的内容是关于JavaScript深度优先遍历(DFS)和广度优先遍历(BFS)算法的介绍,有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。
快递 打印 源码,vscode图标在哪,ubuntu input,tomcat配置cmd,sqlite是免费的么,unity3d ngui 插件下载,有什么好用的前端开发框架,房子里有很多小爬虫,php 框架开发,seo培训课推广,织梦怎么修改网站模板,网页快速定位代码,医院挂号html模板lzw
背景:在开发页面的时候,我们有时候会遇到这种需求:在页面某个dom节点中遍历,找到目标dom节点,我们正常做法是利用选择器document.getElementById(),document.getElementsByName()或者document.getElementsByTagName(),但在本文,我们从算法的角度去查找dom节点,同时理解一下深度优先遍历(DFS)和广度优先遍历(BFS)的原理。
影视视频网站源码html,关闭vscode自动保存,ubuntu软连接,tomcat 不起包,sqlite建表没有设置主键,会卷起来的爬虫叫什么,php 匹配div,长沙网络seo优化企业,阿里云jsp网站模板,b2b h5模板下载lzw
准备
假设页面上的dom结构如下:
让我们来把这个dom结构转化成树的样子
这样之后,dom结构似乎清楚了不少。
深度优先遍历(Depth-First Search)
该方法是以纵向的维度对dom树进行遍历,从一个dom节点开始,一直遍历其子节点,直到它的所有子节点都被遍历完毕之后在遍历它的兄弟节点。即如图所示(遍历顺序为红字锁标):
js实现该算法代码(递归版本):
function deepFirstSearch(node,nodeList) {if (node) { nodeList.push(node); var children = node.children; for (var i = 0; i < children.length; i++) //每次递归的时候将 需要遍历的节点 和 节点所存储的数组传下去 deepFirstSearch(children[i],nodeList); } return nodeList; }
非递归版本:
function deepFirstSearch(node) { var nodes = []; if (node != null) { var stack = []; stack.push(node); while (stack.length != 0) { var item = stack.pop(); nodes.push(item); var children = item.children; for (var i = children.length - 1; i >= 0; i--) stack.push(children[i]); } } return nodes;}
deepFirstSearch接受两个参数,第一个参数是需要遍历的节点,第二个是节点所存储的数组,并且返回遍历完之后的数组,该数组的元素顺序就是遍历顺序,调用方法:
let root = document.getElementById( oot)deepTraversal(root,nodeList=[])
控制台输出结果
广度优先遍历(breadth-first traverse)
该方法是以横向的维度对dom树进行遍历,从该节点的第一个子节点开始,遍历其所有的兄弟节点,再遍历第一个节点的子节点,完成该遍历之后,暂时不深入,开始遍历其兄弟节点的子节点。即如图所示(遍历顺序为红字锁标):
js实现算法代码(递归版本):
function breadthFirstSearch(node) { var nodes = []; var i = 0; if (!(node == null)) { nodes.push(node); breadthFirstSearch(node.nextElementSibling); node = nodes[i++]; breadthFirstSearch(node.firstElementChild); } return nodes;}
递归版本的BFS由于层级太深,会导致堆栈溢出:Maximum call stack size exceeded,但遍历的顺序依旧没有问题,可以在遍历过程中进行操作,不返回遍历数组即可。
非递归版本:
function breadthFirstSearch(node) {var nodes = [];if (node != null) {var queue = [];queue.unshift(node);while (queue.length != 0) { var item = queue.shift(); nodes.push(item); var children = item.children; for (var i = 0; i < children.length; i++) queue.push(children[i]);}}return nodes; }
控制台输出结果:
总结:BFS和DFS都是图的算法之一,本文所阐述的版本较为简单,为无向且非连通图,在日后会更新更多基于JavaScript的算法。
本篇文章到这里就已经全部结束了,更多其他精彩内容可以关注PHP中文网的JavaScript视频教学栏目!
如果觉得《JavaScript深度优先遍历(DFS)和广度优先遍历(BFS)算法的介绍》对你有帮助,请点赞、收藏,并留下你的观点哦!