JavaScript 中使用递归的 BFS

Question

使用递归进行 DFS 很容易：

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

然而，我见过的 BFS 的每个例子都使用队列，并且是迭代的而不是递归的。想知道是否有任何方法可以定义递归 BFS 算法。

Answer 1

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

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

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))