最新消息:阿里云双12优惠,史上最低折扣。

深度优先搜索的理解与实现

服务器租用 aliyun 121浏览

为何推出云会员?使用会员制有何优势?

云计算走进生活,云产品改变生活的方方面面。云计算正在迅速取代传统计算,就像计算机、服务器和复杂的软件取代了更传统的办公设备一样,云正在取代和简化当今的办公方式。

深度优先搜索作为广度优先搜索的好基友,同样也是对图进行搜索的一种算法。善用这两种算法,可以解决我们业务中遇到的「树形结构遍历搜索」问题。

本文将以图文的形式,详细讲解深度优先搜索,将其与广度优先搜索进行对比,分析两种算法的差异,并用JavaScript将其实现,欢迎各位感兴趣的前端开发者阅读本文。

一、概念

深度优先搜索是一个对图进行搜索的算法。

深度优先搜索与广度优先搜索一样,都是从图的起点开始搜索直到到达目标结点,深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止,然后再折返,开始搜索下一条候补路径。

二、图解示例

如图所示,我们想找G结点在图中的位置。

 

图解示例1

将A结点直达的三个结点B、C、D设为下一步的候补顶点

 

图解示例2

在候补顶点中选择最后成为候补的结点

 

图解示例3

移动选中的顶点到B

 

图解示例4

将可以从B直达的两个结点E和F设为候补顶点

 

图解示例5

此时最后成为B的直达结点的是E,我们将当前点移动至E

 

图解示例6

将可从E直达的顶点K设为候补顶点

 

图解示例7

重复上述操作直到到达终点,或者所有结点都被遍历为止

此时结点到达了F,从A到F的搜索顺序为

A -> B -> E -> K

B -> F

 

图解示例8

此时搜索到了结点

 

图解示例9

到达终点G,搜索结束

 

图解示例10

用JS实现深度优先搜索

正如图解示例所示,深度优先搜索会先将当前结点的直接子结点作为候选结点,挑选出最后加入的子结点,顺着挑选出来的结点一直往下找,直至没有子结点,返回上一级继续寻找其候选结点,直至所有结点都被找完或者取出的结点等于目标结点则搜索结束。

操作候选结点时,我们采用的是最后加入的子结点,也就是后入先出,满足了栈这种数据结构,因此可以「栈」来管理候选顶点。

声明一个函数,参数为:需要查找的树,需要查找的结点

用数组模拟栈,将要查找的树放入栈中

遍历栈,直至栈中的数据为空

取出栈顶元素,判断其是否有子结点

如果存在子结点,遍历子结点将其放入栈中,遍历时需要确保它是从左到右遍历

判断当前栈顶的元素是否与要查找的元素相等,如果相等则返回当前元素

栈中数据全部遍历后,还是没找到目标结点,则证明目标结点不在树中,返回false。

接下来,我们将上述思路转换为代码:

/**

 * 深度优先搜索

 * @param tree 需要查找的树

 * @param target 需要查找的结点

 * @returns {{children}|*|undefined|boolean}

 */

function depthFirstSearch (tree, target) {

    // 用数组模拟栈,将树放进栈中

    let stack = [tree];

    while(stack.length!==0){

        // 取出数组的最后一个元素(栈顶)

        const stackTop = stack.pop();

        // 判断当前栈是否有子结点

        if (stackTop.children && stackTop.children.length) {

            /**

             * 将子结点入栈:

             *  1. 使用扩展运算符取出参数对象,使用reverse方法将数组中的元素进行颠倒

             *  2. 使用扩展运算符取出颠倒后数组中的对象

             *  3. 将取出的对象放进栈中

             */

            stack.push(…[…stackTop.children].reverse());

        }

        // 判断当前栈顶的元素是否为目标值

        if (stackTop.value === target) {

            return stackTop;

        }

    }

    return false;

}

接下来,我们用上一篇文章:广度优先搜索的理解与实现中的例子,来测试下我们编写的广度优先搜索函数

const targetVal = depthFirstSearch(dataTree,”天河区”);

if(targetVal !==false){

    console.log(`目标结点的数据: `);

    console.log(targetVal);

}else{

    console.log(`目标结点不存在`);

}

深度优先搜索与广度优先搜索的区别

对广度优先搜索不了解的开发者请移步 => 广度优先搜索的理解与实现

本质区别

深度优先搜索:沿着一条路径不断往下,进行深度搜索。

广度优先搜索:顺着边不断进行搜索,直至找到目标结点。

候补顶点的选择

「广度优先搜索」选择的是最早成为候补的顶点,因为顶点离起点越近就越早成为候补,所以会从离起点近的地方开始按顺序搜索。

「深度优先搜索」选择的是最新成为候补的顶点,所以会一路往下,沿着新发现的路径不断深入搜索。

转载请注明:小猪云服务器租用推荐 » 深度优先搜索的理解与实现