n叉树中BFS的复杂度

Question

我正在寻找在 O(n) 中对 n 叉树进行 BFS 的算法，我找到了以下算法，但是我在分析时间复杂度时遇到了问题。我不确定它是 O(n) 还是 O(n^2)。有人可以解释时间复杂度或给出替代算法，其中运行 in O(n)

谢谢

breadthFirstSearch = (root, output = []) => {
  if (!root) return output;
  const q = new Queue();
  q.enqueue(root);
  while (!q.isEmpty()) {

    const node = q.dequeue();
    
    output.push(node.val);
    
    for (let child of node.children) {
      q.enqueue(child);
    }
  }
  return output;
};

Answer 1

这确实是一个泛型树的BFS算法。如果你定义为in-ary tree，那么时间复杂度与那个无关。

但是，如果表示树中的节点总数，则时间复杂度为 O()，因为每个节点恰好入队一次，恰好出队一次。由于队列操作是O(1)，所以时间复杂度是O()。

n叉树中BFS的复杂度

Complexity of BFS in n-ary tree

algorithm

tree

breadth-first-search

time-complexity