vlambda博客
学习文章列表

深度优先、广度优先对于理解相对复杂，我们从实际问题出发，先看下常用的两个例子热热身。

例一、实现将多维数组转换成一维数组的flat方法？

深度优先遍历

let arr = ['a', ['b', 'c', ['d', 'e', 'f', ['g']]]];
function dfsFlat(array){
    let arr = [];
    let queue = array;
    if(!queue.length){
        return [];
    }
    while(queue.length){
        let val = queue.pop();
        console.log(val);  // => ???
        if(Array.isArray(val)){
            queue.push(...val);
        }else{
            arr.unshift(val);
        }
    }
    return arr;
}
dfsFlat(arr);

广度优先遍历

let arr = ['a', ['b', 'c', ['d', 'e', 'f', ['g']]]];
function bfsFlat(array){
    let arr = [];
    let queue = array;
    if(!queue.length){
        return [];
    }
    while(queue.length){
        let val = queue.shift();
        console.log(val);  // => ???
        if(Array.isArray(val)){
            queue.push(...val);
        }else{
            arr.push(val);
        }
    }
    return arr;
}
bfsFlat(arr);

例二、遍历data树形节点？

let data = [
    {
        name: 'a1',
        children: [
            { name: 'b11', children: [{ name: 'qdkc111'}]},
            { name: 'b12', children: [{ name: 'qdkc121'}]},
            { name: 'b13', children: [{ name: 'qdkc131'}]},
        ],
    },
    {
        name: 'a2',
        children: [
            { name: 'b21', children: [{ name: 'qdkc211'}]},
            { name: 'b22', children: [{ name: 'qdkc221'}]},
            { name: 'b23', children: [{ name: 'qdkc231'}]},
        ]
    }
];

深度优先遍历

let data = [{name:'a1',children:[{name:'b11',children:[{name:'qdkc111'}]},{name:'b12',children:[{name:'qdkc121'}]},{name:'b13',children:[{name:'qdkc131'}]},],},{name:'a2',children:[{name:'b21',children:[{name:'qdkc211'}]},{name:'b22',children:[{name:'qdkc221'}]},{name:'b23',children:[{name:'qdkc231'}]}]}];
function dfsTraversal(node){
    let stack = [];
    let nodes = [];
    if (node) {
        stack.push(...node);
        while (stack.length) {
            let item = stack.pop();
            console.log(item);  // => ???
            nodes.push(item);
            let children = item.children;
            if (children) {
                for (let i = children.length - 1; i >= 0; i--) {

                    stack.push(children[i]);
                }
            }
        }
    }
    return nodes;
}
dfsTraversal(data);

广度优先遍历

let data = [{name:'a1',children:[{name:'b11',children:[{name:'qdkc111'}]},{name:'b12',children:[{name:'qdkc121'}]},{name:'b13',children:[{name:'qdkc131'}]},],},{name:'a2',children:[{name:'b21',children:[{name:'qdkc211'}]},{name:'b22',children:[{name:'qdkc221'}]},{name:'b23',children:[{name:'qdkc231'}]}]}];
let bfsTraversal = function(node){
    let nodes = [];
    let stack = [];
    if (node) {
        stack.push(...node);
        while (stack.length) {
            let item = stack.shift()
            console.log(item);  // => ???
            nodes.push(item);
            let children = item.children;
            if(children){
                for (let i = 0; i < children.length; i++) {
                    stack.push(children[i])
                }
            }
        }
    }
    return nodes;
}
bfsTraversal(data);

「原理」广度遍历BFS是「队列」实现，先进先出。深度遍历DFS是用「栈」实现，先进后出。

广度遍历步骤

广度优先搜索使用队列（queue）来实现，整个过程也可以看做一个倒立的树形：

• 1、把根节点放到队列的末尾。
• 2、每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。
• 3、找到所要找的元素时结束程序。
• 4、如果遍历整个树还没有找到，结束程序。

深度遍历步骤

深度优先搜索用栈（stack）来实现，整个过程可以想象成一个倒立的树形：

• 1、把根节点压入栈中。
• 2、每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱。
• 3、找到所要找的元素时结束程序。
• 4、如果遍历整个树还没有找到，结束程序。

工作中非常实用且重要的例子，建议收藏，方便日后查找阅读。