深度优先遍历,广度优先遍历实现对象的深拷贝
深度优先遍历
深度优先遍历(depth-first-search),是搜索算法的一种,它沿着树的深度遍历树的节点,尽可能深地搜索树的分支。当节点v的所有边都已被探寻过,将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已探寻源节点到其他所有节点为止,如果还有未被发现的节点,则选择其中一个未被发现的节点为源节点并重复以上操作,直到所有节点都被探寻完成。
简单的说,dfs就是从图中的一个节点开始追溯,直到最后一个节点,然后回溯,继续追溯下一条路径,直到到达所有的节点,如此往复,直到没有路径为止。
dfs和bfs一般是用来解决图的遍历的,但是在这里,既然是前端,我是用dfs和bfs来遍历dom树。
下面采用栈的形式或者递归的形式实现:
dom节点
<div class="parent"> <div class="c-1"> <div class="c-1-1"> </div> <div class="c-1-2"> </div> <div class="c-1-3"> </div> <div class="c-1-4"> </div> <div class="c-1-5"> </div> </div> <div class="c-2"> <div class="c-2-1"> </div> <div class="c-2-2"> </div> <div class="c-2-3"> </div> <div class="c-2-4"> <div class="c-2-4-1"> </div> <div class="c-2-4-2"> </div> <div class="c-2-4-3"> </div> <div class="c-2-4-4"> </div> <div class="c-2-4-5"> </div> </div> <div class="c-2-5"> </div> </div> <div class="c-3"> </div> <div class="c-4"> </div> </div>
dfs实现
var node = document.queryselectorall('.parent')[0]; //递归写法 function dfs1 (node, nodelist = []){ if (node != null){ nodelist.push(node); let children = node.children for(let i = 0; i < children.length; i++){ dfs1(children[i], nodelist) } } return nodelist } let nodelist = dfs1(node); console.log(nodelist); //栈写法 function dfs2(node){ let nodelist = []; if (node){ //栈 后进先出 let stack = []; stack.push(node); while (stack.length) { let _node = stack.pop(); nodelist.push(_node); let children = _node.children; //这样写是从右向左 // for (let i = 0; i < children.length; i++) { // stack.push(children[i]); // } //从左向右 for (let i = children.length-1; i >= 0; i--) { stack.push(children[i]); } } } return nodelist; } let nodelist2 = dfs2(node); console.log(nodelist2);
运行结果,上面dfs1和dfs2的结果是一样的
广度优先遍历
广度优先遍历(breadth-first-search)是从根节点开始,沿着图的宽度遍历节点,如果所有节点均被访问过,则算法终止,bfs 同样属于盲目搜索,一般用队列数据结构来辅助实现bfs。
还是采用上面的dom节点。bfs的写法如下。
代码采用队列的形式实现。
var node = document.queryselectorall('.parent')[0]; function bfs1(node, nodelist = []) { if (!node){ return; } //队列 先进先出 var sequeue = []; sequeue.push(node); while (sequeue.length){ var _node = sequeue.shift(); nodelist.push(_node) for(var i = 0; i < _node.children.length; i++){ sequeue.push(_node.children[i]) } } return nodelist } let nodelist = bfs1(node); console.log(nodelist);
结果如下
下面采用两种方式来实现对象深度克隆的实现。
dfs深度克隆
深度克隆要注意两个问题
1、环状数据问题:如果一个对象具有环状对象,比如obj.a.b.c === obj.a
,就会使递归进入死循环,从而导致爆栈错误。
2、边界处理: 对象中不止原始类型,还存在如函数、set等数据类型,我们需要一一做处理。下面代码只是解决了对函数的复制。
let _tostring = object.prototype.tostring; let map = { array: 'array', object: 'object', function: 'function', string: 'string', null: 'null', undefined: 'undefined', boolean: 'boolean', number: 'number' } function gettype(obj){ return _tostring.call(obj).slice(8, -1) } function istypeof(obj, type){ return map[type] && map[type] === gettype(obj) } //深度克隆 //深度优先遍历 /** * * 解决三个问题 递归问题 环状数据问题 边界处理(比如函数,set等) */ const dfsdeepclone = function (obj, visitedarr = []){ let _obj = {}; if (istypeof(obj, 'array') || istypeof(obj, 'object')){ let index = visitedarr.indexof(obj); if (index > -1){ _obj = visitedarr[index] } else{ visitedarr.push(obj) for (let key in obj){ _obj[key] = dfsdeepclone(obj[key], visitedarr) } } } else if(istypeof(obj, 'function')){ _obj = eval( '(' + obj.tostring() + ')')//处理函数 } else{ _obj = obj;//处理原始值 } return _obj; } let testobj = { a: 1, b: { c: 1, d: 2 }, circle: null, e: function() { console.log(1); } } let clonetestobj = dfsdeepclone(testobj); let clonetestobj2 = testobj; console.log(clonetestobj); console.log('经过深度克隆后的更改'); clonetestobj.b = {};//经过深度克隆后的更改 console.log(clonetestobj); console.log(testobj); clonetestobj2.b = {}; //引用的更改 console.log('引用的更改'); console.log(clonetestobj2); console.log(testobj); //环状数据 let testcircle = { a: 1, b: { c: 1, d: 2, circle: null, }, e: function() { console.log(1); } } testcircle.b.circle = testcircle.b; clonetestcircle = dfsdeepclone(testcircle);//不处理环问题是会爆栈的 进入死循环 console.log(clonetestcircle);
bfs深度克隆
let _tostring = object.prototype.tostring; let map = { array: 'array', object: 'object', function: 'function', string: 'string', null: 'null', undefined: 'undefined', boolean: 'boolean', number: 'number' } function gettype(obj){ return _tostring.call(obj).slice(8, -1) } function istypeof(obj, type){ return map[type] && map[type] === gettype(obj) } //广度优先深度克隆, 利用队列的方式实现 //利用copyobj建立一个与原对象相同的数据结构, 遇到可处理的值(比如原始值,函数,就处理后赋值到相应的节点下) const bfsdeepclone = function (obj, visitedarr = []){ let copyobj = {}; let sequeue = [obj];//进队列 //同时copyobj也跟着一起进队列 let copysequeue = [copyobj]; while(sequeue.length){ let _obj = sequeue.shift(); let _copyobj = copysequeue.shift(); if (istypeof(_obj, 'array') || istypeof(_obj, 'object')){ for(item in _obj){ let val = _obj[item]; if (istypeof(val, 'object')){ let index = visitedarr.indexof(val) if (~index){ //是环形数据 _copyobj[item] = visitedarr[index]; } else{ //新的对象,给copyobj一个对应属性的空对象 sequeue.push(val); _copyobj[item] = {}; copysequeue.push(_copyobj[item]); visitedarr.push(val); } } else if (istypeof(val, 'array')){ sequeue.push(val); _copyobj[item] = []; copysequeue.push(_copyobj[item]) } else if(istypeof(val, 'function')){ _copyobj[item] = eval( '(' + val.tostring() + ')');//处理函数 } else{ _copyobj[item] = val;//处理原始值 } } } else if(istypeof(obj, 'function')){ _copyobj = eval( '(' + _obj.tostring() + ')');//处理函数 } else{ _copyobj = _obj;//处理原始值 } } return copyobj } let testobj = { a: 1, b: { c: 1, d: 2 }, circle: null, e: function() { console.log(1); } } let clonetestobj = bfsdeepclone(testobj); let clonetestobj2 = testobj; console.log(clonetestobj); //环状数据 let testcircle = { a: 1, b: { c: 1, d: 2, circle: null, }, e: function () { console.log(1); } } testcircle.b.circle = testcircle.b; clonetestcircle = bfsdeepclone(testcircle);//不处理环问题是会爆栈的 进入死循环 console.log(clonetestcircle); /** * 打印如下 { a: 1, b: { c: 1, d: 2 }, circle: null, e: [function] } { a: 1, b: { c: 1, d: 2, circle: { c: 1, d: 2, circle: [circular] } }, e: [function] } */
上一篇: 改变font-weight的数值,样式并不会改变的原因
下一篇: 显示方式
推荐阅读
-
Java实现二叉树的深度优先遍历和广度优先遍历算法示例
-
深度优先遍历,广度优先遍历实现对象的深拷贝
-
PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
-
PHP实现二叉树的深度优先与广度优先遍历方法
-
深度优先遍历,广度优先遍历实现对象的深拷贝
-
【数据结构】图的遍历——深度优先搜索DFS、广度优先搜索BFS
-
数据结构与算法————图的遍历DFS深度优先搜索和BFS广度优先搜索
-
(浙大-19-夏-数据结构学习笔记+代码)图的遍历+深度优先+广度优先(Graph)
-
JavaScript实现树的遍历算法示例【广度优先与深度优先】
-
PHP实现基于图的深度优先遍历输出1,2,3...n的全排列功能