通过 题目 deepCount 理解深度优先以及广度优先

[cjfff]

前言

为什么要写此文章呢？

深度优先，广度优先，每当看到这一词汇我都会觉得高大上..... 但遇到的多了，总想把它搞个明白, 某次做题的时候算是想明白了，所以记下来，免得下次还是忘记，也希望能给一些有同样困惑的小伙伴带来帮助.

如果有小伙伴连概念都不懂...那就直接去维基百科吧，毕竟那里比我解释的要明白~ 广度优先遍历 深度优先遍历

题目

解析

首先这当时做的一个题目，为了能更好的说明问题，输入参数上我作了点适当的修改

const arr = ["x", ['a', 'b', ['c']], ["y", ['d']], ["z"]]

用树来表示就是下面的形式

深度优先

深度优先实现起来比较简单，大白话就是找到一个节点，一直递归到底部，再进行下一个节点的遍历递归

走向图如下

上代码~~

// 深度优先
const deepCount = (A, count = 0) => {
  A.forEach(item => {
    Array.isArray(item) && (count += deepCount(item))
    count++
  });
  return count
}

如果想看清除代码走向，骚做修改就可以实现

const deepCount = (A, count = 0, path = []) => {
  A.forEach(item => {
    if (Array.isArray(item)) {
      count += deepCount(item, 0, path)
    } else {
      path.push(item)
    }
    count++
  });
  console.log(path);
  return count
}

const arr = ["x", ['a', 'b', ['c']], ["y", ['d']], ["z"]]

deepCount(arr) // [ 'x', 'a', 'b', 'c', 'y', 'd', 'z' ]

可以看到是完全符合上面的走向预期的

广度优先

广度优先的话就是走完平级节点再往下走.....表述应该不太好

走向图

// 广度优先
const deepCount = (A, count = 0) => {
  const taskList = [A]

  while (taskList.length) {
    const arr = taskList.shift()
    arr.forEach((item) => {
      Array.isArray(item) && taskList.push(item)
      count++
    })
  }
  return count
}

验证

const deepCount = (A, count = 0, path = []) => {
  const taskList = [A]

  while (taskList.length) {
    const arr = taskList.shift()
    arr.forEach((item) => {
      if (Array.isArray(item)) {
        taskList.push(item)
      } else {
        path.push(item)
      }
      count++
    })
  }
  console.log(path);
  return count
}

const arr = ["x", ['a', 'b', ['c']], ["y", ['d']], ["z"]]

console.log(deepCount(arr)); // [ 'x', 'a', 'b', 'y', 'z', 'c', 'd' ]

总结: 至此，我们利用深度优先与广度优先解决了问题，撒花★,°:.☆(￣▽￣)/$:.°★ 。

最后贴下部门的每日一题活动~~~ spaas-daily-practice