深度优先搜索作为广度优先搜索的好基友,同样也是对图进行搜索的一种算法。善用这两种算法,可以解决我们业务中遇到的「树形结构遍历搜索」问题。
本文将以图文的形式,详细讲解深度优先搜索,将其与广度优先搜索进行对比,分析两种算法的差异,并用JavaScript将其实现,欢迎各位感兴趣的前端开发者阅读本文。
深度优先搜索是一个对图进行搜索的算法。
深度优先搜索与广度优先搜索一样,都是从图的起点开始搜索直到到达目标结点,深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止,然后再折返,开始搜索下一条候补路径。
如图所示,我们想找G结点在图中的位置。
A -> B -> E -> K
B -> F
82c0b4231154b9a2db65e30ca29acaa9.png
正如图解示例所示,深度优先搜索会先将当前结点的直接子结点作为候选结点,挑选出最后加入的子结点,顺着挑选出来的结点一直往下找,直至没有子结点,返回上一级继续寻找其候选结点,直至所有结点都被找完或者取出的结点等于目标结点则搜索结束。
操作候选结点时,我们采用的是最后加入的子结点,也就是后入先出,满足了栈这种数据结构,因此可以「栈」来管理候选顶点。
❝接下来,我们将上述思路转换为代码: ❞
/**
* 深度优先搜索
* @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(`目标结点不存在`);
}
执行结果.png
对广度优先搜索不了解的开发者请移步 => 广度优先搜索的理解与实现
深度优先搜索:沿着一条路径不断往下,进行深度搜索。
广度优先搜索:顺着边不断进行搜索,直至找到目标结点。
「广度优先搜索」选择的是最早成为候补的顶点,因为顶点离起点越近就越早成为候补,所以会从离起点近的地方开始按顺序搜索。
「深度优先搜索」选择的是最新成为候补的顶点,所以会一路往下,沿着新发现的路径不断深入搜索。