欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

深度优先遍历,广度优先遍历实现对象的深拷贝

程序员文章站 2022-10-13 09:36:55
深度优先遍历(Depth-First-Search),是搜索算法的一种,它沿着树的深度遍历树的节点,尽可能深地搜索树的分支。当节点v的所有边都已被探寻过,将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已探寻源节点到其他所有节点为止,如果还有未被发现的节点,则选择其中一个未被发现的节点为源节... ......

深度优先遍历

深度优先遍历(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]
}
*/