javascript - 使用递归在 JavaScript 中进行 BFS

Question

使用递归很容易做DFS:

function dfs(tree, fn, level) {
  fn(tree, level)
  tree.children.forEach(function(child){
    dfs(child, fn, level + 1)
  })
}

但是每个example我看到 BFS 使用队列并且是迭代的而不是递归的。想知道是否有任何方法可以定义递归 BFS 算法。

Answer 1

如果兄弟节点可以排序并且有信息或方法来检索关于他们的兄弟节点的信息，我们可以按照广度优先搜索的顺序执行。显然，使用抽象数据，边走边建树，就像计算后续的国际象棋走法一样，这可能是不可能的或过于复杂。然而，树数据结构可以在提供兄弟信息的情况下构建。

这是一个带有虚拟“兄弟”和“完成”功能的示例。如果我们不能保证每个节点都有 child ，我们可能需要一个额外的参数来记录最后看到的 child 。请注意，“下一个兄弟”可能类似于链表，但也可以实现为一种基于已知信息计算下一个兄弟是什么的方法。

function bfs(tree, fn) {
  fn(tree);
  
  if (tree.done) return;
  
  if (tree.isLastSibling)
    bfs(tree.children.firstSibling(), fn);
  else
    bfs(tree.nextSibling(), fn);
}

var c4 = {
  val: 'c4',
  isLastSibling: true,
  done: true
}

var c3 = {
  val: 'c3',
  nextSibling: () => c4
}

var c2 = {
  val: 'c2',
  nextSibling: () => c3
}

var c1 = {
  val: 'c1',
  nextSibling: () => c2
}

var b2 = {
  val: 'b2',
  isLastSibling: true,
  children: {firstSibling: () => c1}
}

var b1 = {
  val: 'b1',
  nextSibling: () => b2
}

var a = {
  val: 'a',
  isLastSibling: true,
  children: {firstSibling: () => b1}
}

bfs(a, tree => console.log(tree.val))