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' 函数的示例。如果我们不能保证每个节点都有 children，我们可能需要一个额外的参数来记录最后看到的 child。请注意，'next sibling' 可以类似于链表，但也可以实现为一种基于已知信息计算下一个兄弟姐妹的方法。

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

JavaScript 中的 BFS 使用递归

BFS in JavaScript using Recursion

javascript

algorithm

tree

breadth-first-search

tree-traversal