DFS.md

深度优先搜索

深度优先搜索算法（DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止

算法图示

算法思想

1. 首先将根节点放入队列中
2. 从队列中取出第一个节点，并检验它是否为目标。如果找到目标，则结束搜寻并回传结果，否则将它某一个尚未检验过的直接子节点加入队列中
3. 重复步骤2
4. 如果不存在未检测过的直接子节点，将上一级节点加入队列中，重复步骤2
5. 重复步骤4
6. 若队列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”

打个比方，使用深度优先搜索公司的组织架构。有CEO、董事长1、董事长2....那么搜索顺序就是从最顶级的CEO开始，然后开始搜索他的下级董事长1（从左往右数，也就是1、2、3...），然后继续搜索董事长1的下级，依然从最左开始，直到最底层员工，然后开始依次向右搜索

代码实现

const obj = [{
  value: '1',
  children: [{
    value: '1-1'
  }, {
    value: '1-2',
    children: [{
      value: '1-2-1'
    }]
  }]
}, {
  value: '2'
}, {
  value: '3',
  children: [{
    value: '3-1',
    children: [{
      value: '3-1-1'
    }, {
      value: '3-1-2',
      children: [{
        value: '3-1-2-1'
      }]
    }]
  }]
}]

// 深度优先搜索
function DFS(tree, nodes = []) {
  for (key in tree) {
    let value = tree[key]
    if (typeof value === 'string') nodes.push(value) // 这里对应的业务逻辑是string,根据实际情况判断
    else DFS(value, nodes)
  }
  return nodes
}

<!-- 输出结果：可以看到，先把1遍历完，然后开始2、3，每一层都是这样，如此往复
[ '1',
  '1-1',
  '1-2',
  '1-2-1',
  '2',
  '3',
  '3-1',
  '3-1-1',
  '3-1-2',
  '3-1-2-1' ]
  -->