手记

BFS 与 DFS

  休息了一个月,本月开始正常更新,这一篇来聊一下DFS和BFS。

  首先大致提一下这两个英文单词首字母缩写的含义。

  DFS(Deep First Search):即深度优先搜索

  BFS(Breath First Search):即广度优先搜索(遍历)

  在一些科幻的电视或小说中,可能经常会遇到这样的情景,主角跟着一群伙伴去探宝,但宝物不是那么容易拿的,有一道道的关卡,甚至这之中不乏有生门,死门这样可能选错再也没有回头路的关口,怎样走才能走到目的地,取到宝物呢?

  通常有两种做法:

  第一种,往某一条路一直走,走到黑,等发现没有宝物再折(回溯)回来,继续往另一条路一直走走到黑,如此一直循环并最终找到宝物。

  这种做法强调的是关卡的深度。此时程序扫描的路径是往深处扫描的,除非碰到这条路径的最尽头,此时回源头继续往;另一条路径上扫

  第二种:派出多个人分各条路去走,每走一关随时汇报情况。

  这种做法强调的是关卡的广度。此时程序扫描的路径是从最外层

  这个其实说的就是DFSBFS

  BFS跟DFS在树结构的遍历或检索中非常常见,我们一起来写一个DFS和BFS的实现过程,体会一下这两个优秀的搜索思想。

这是我们要搜索的树结构,假设我现在想要搜索到id为1111的那条数据的name值。

tree.js

展开查看

export const Tree = [
    {
        id: "1",
        name: "xiaoming",
        children: [
            {
                id: "11",
                name: "xiaohua",
                children: [
                    {
                        id: "111",
                        name: "xiaohong",
                        children: [
                            {
                                id: "1111",
                                name: "xiaoqiang",
                                children: [
                                    {
                                        id: "11111",
                                        name: "xiaozhao"
                                    },
                                    {
                                        id: "11112",
                                        name: "xiaoxin"
                                    },
                                ]
                            }
                        ]
                    }
                ]
            },
            {
                id: "12",
                name: "xiaotian",
                children: [
                    {
                        id: "121",
                        name: "xiaohe"
                    }
                ]
            },
            {
                id: "13",
                name: "xiaoli",
                children: [
                    {
                        id: "131",
                        name: "xiaobing",
                        children: [
                            {
                                id: "1311",
                                name: "xiaoqin"
                            }
                        ]
                    }
                ]
            },
        ]
    },
    {
        id: "2",
        name: "xiaoyi",
        children: [
            {
                id: "21",
                name: "xiaobi",
                children: [
                    {
                        id: "211",
                        name: "xiaosheng",
                        children: [
                            {
                                id: "2111",
                                name: "xiaoguang",
                                children: [
                                    {
                                        id: "21111",
                                        name: "xiaomi"
                                    },
                                    {
                                        id: "21112",
                                        name: "xiaoxing"
                                    },
                                ]
                            }
                        ]
                    }
                ]
            },
            {
                id: "22",
                name: "xiaozhong",
                children: [
                    {
                        id: "221",
                        name: "xiaoqing"
                    }
                ]
            },
            {
                id: "23",
                name: "xiaogua",
                children: [
                    {
                        id: "231",
                        name: "xiaoguai",
                        children: [
                            {
                                id: "2311",
                                name: "xiaolin"
                            }
                        ]
                    }
                ]
            },
        ]
    }
]

  上面是一个很常见的树结构简化版。

  要找到我们想要的那条目标数据,通过BFS,来查找会怎样呢?看看:


export class BFS {

    constructor (tree, target) {

        this.tree = tree;

        this.flag = true;

        this.count = 0;

        this.init(target);
    }

    init (target) {

        this.flag && this.breathFirst(this.tree, target);

        console.log("this.count = " + this.count);
    }

    breathFirst (nodeList, target) {

        let nextNodeList = [];

        for(let item of nodeList) {

            this.count ++;

            if(item.id === target) {

                console.log(item.name);

                this.flag = false;

                return;
            }

            if( !!item.children && item.children.length) {

                nextNodeList.push(...item.children);
            }
        }
        
        this.flag && nextNodeList.length && this.breathFirst(nextNodeList, target);
    }
}

  BFS: 广度优先,你会发现最终程序的扫描是扫到1,接着扫描到2,这时候第一层的扫完了,开始扫第二层,一直下去…广度在这里的优先级更高。
  而它的实现其实也不难,就是需要一个动态的数组,去储存每一层中所有路径上关卡的信息,并用于下一次的继续探索。

  再来看一下DFS深度优先,


export class DFS {

    constructor (tree, target) {

        this.tree = tree;

        this.count = 0;

        this.flag = true;

        this.init(target);
    }

    init (target) {

        this.tree.forEach(item => {

            // 可以尝试一下这里的目标id传入11112跟12的区别,可以很简单的看出11112的this.count更小,深度优先
            // this.flag && this.deepFirst(item, "11112");

            this.flag && this.deepFirst(item, target);
        });

        console.log("this.count = " + this.count);
    }

    deepFirst (node, target) {

        this.count ++;

        if(node.id === target) {

            console.log(node.name);

            this.flag = false;

            return;
        }

        if( !!node.children && !!node.children.length ) {

            node.children.forEach(item => this.flag && this.deepFirst(item, target));
        }
    }
}

  DFS,这时候你可以发现深度遍历是先扫描到1,1这里这条路径还没有到尽头,继续走,到11,继续直到11111的时候撞墙了,才会回头。深度在这里是受到优先待遇的。
  而它的实现很简单很粗暴,一条路径不就是一直是if有children,go,并且不断的将children里的各项作为新的参数递归传递给同一函数,当碰到目标值,直接return出来就好了。这个过程如果目标值是唯一的,那直接像设置一个flag值也就OK了。如果不唯一其实也好办,直接给扫描到的目标值加标记就好了,等多个目标值全部都是新标记的,则是程序跳出执行的时候。至于拿到目标之后需要做什么,则由各自的业务去决定了。

  说到这,关于DFS和BFS,其实还有另一个更为形象的现实例子,那就是 —— 剥玉米

  你有若干个玉米,玉米本身还有很多层,某个玉米有一层被涂上了红色的标记,现在你需要找到这一层

  此时:

  深度优先(DFS)的意思就是你先随机抽一个玉米,一层层的剥皮,直到尽头若还没有红色标记,继续拿剩余的玉米重复操作。强调的是深

  广度优先(BFS)的意思则是你将所有的玉米都先剥出来一层皮,看看有没有有红色标记的,没有,继续剥第二层,一直下去…。强调的是广

  而这两者的性能是根据实际情况不同而不同的,如果某些业务场景,假如可以预见目标出现的层数级别不会很深,此时采用BFS可能效果更好。

  而在一些结构偏窄且更为深的树结构上,此时采用DFS可能可以更快达到目的。

  这样一想,DFS跟BFS是不是其实没有什么,挺好理解的,对不?

  最后补充一下上面代码的入口与调用。


import { Tree } from './tree.js';

import { DFS } from './DFS.js';

import { BFS } from './BFS.js';

export const Api = {

    init () {

        this.tree = Tree;

        this.breathFirstSearch();

        this.deepFirstSearch();
    },
    breathFirstSearch () {

        console.log("=============== BFS ==================");

        let tree = JSON.parse(JSON.stringify(this.tree));

        new BFS(tree, "1");     //  1
        new BFS(tree, "2");     //  2
        new BFS(tree, "11");    //  3
        new BFS(tree, "12");    //  4
        new BFS(tree, "13");    //  5
    },
    deepFirstSearch () {

        console.log("=============== DFS ==================");

        let tree = JSON.parse(JSON.stringify(this.tree));

        new DFS(tree, "1");     //  1
        new DFS(tree, "11");    //  2
        new DFS(tree, "111");   //  3
        new DFS(tree, "1111");  //  4
        new DFS(tree, "11111"); //  5
    }
}

1人推荐
随时随地看视频
慕课网APP