广度优先搜索和深度优先搜索的实现

前言

---

广度优先搜索和深度优先搜索都是对图进行搜索的算法

广度优先搜索

广度优先搜索广泛搜索子节点，将其子节点放进候选节点中；操做候选节点时是按顺序取出候选节点，因此使用队列存储候选节点。关于队列的实现可参考队列的实现

• 声明广度优先搜索函数，参数为要搜索的树形图和要查找的节点
• 实例化队列，声明目标节点的深度，初始化0
• 遍历队列
• 获取队列第一个元素，判断是否和目标节点相等，相等返回深度
• 判断当前节点是否有子节点，并将子节点添加到队列中
• 删除当前队列第一个元素

function breadthFirstSearch(tree, target) {
  //实例化队列
  let queue = new Queue()
  //声明目标节点的深度
  let step = 0
  //搜索树入队
  queue.enqueue(tree)
  //队列不为空就继续搜索
  while(!queue.isEmpty()) {
    //深度加一
    step += 1
    //获取队列长度
    let length = queue.size()
    //遍历队列
    for(let i = 0; i < length; i++) {
      //获取队列第一个元素
      let front = queue.front()
      //判断当前节点是否是要找的节点
      if(target.value === front.value) return step
      //判断当前节点是否有子节点并入队
      if(front.children && front.children.length) {
        front.children.map(item => {
          queue.enqueue(item) 
        }) 
      }
      //删除已遍历过的节点
      queue.dequeue()
    } 
  }
}

广度优先搜索从一个顶点开始，先宽后深的访问节点，因此顶点离起点越近，搜索越快。

深度优先搜索

深度优先搜索将当前节点的直接子节点作为候选节点；操作候选节点时，采用最后加入的子节点，因此使用栈存储候选顶点；栈的实现

• 声明深度优先搜索函数，参数为要搜索的树形图和要查找的节点
• 数组模拟栈，将要搜索的树压入栈中
• 取出栈顶元素，判断是否是要查找的节点 如果是就返回当前节点
• 判断当前节点是否有子节点，翻转子节点组成的数组，压栈

function depthFirstSearch(tree, target) {
  //数组模拟栈,将搜索的树形图压栈
  let stack = [tree]
  while(stack.length !== 0) {
    //获取栈顶顶点
    let stackTop = stack.pop()
    //判断当前顶点是否是要查找的顶点
    if(stackTop.value === target.value) return stackTop
    //判断是否有子节点
    if(stackTop.chilren && stackTop.children.length) {
      //子节点组成的数组翻转，压栈
      stack.push(...[...stack.children].reverse())
    }
    return false
  }
}

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

深度优先搜索：选择最新成为候补的顶点，沿着一条路径搜索到底

广度优先搜索：选择最早成为候补的顶点，沿着边搜索