algorithm - 广度优先搜索和层序遍历有什么区别？

Question

我不需要代码，只需要一个解释。我的教科书说

level order: each node at level i is processed before any node at level i+1

我对广度优先搜索的理解是，从左边开始，首先探索距离根最近的节点？这有什么不同？这是正方形和长方形的情况吗？

Answer 1

对于“正确的”树(见下文)，它是同一回事，至少在大多数定义中是这样。喜欢Wikipedia ，例如:

Breadth-first

See also: Breadth-first search

Trees can also be traversed in level-order, ...

... a breadth-first (level-order) traversal ...

好吧，至少层序遍历与广度优先遍历是一样的。遍历某些东西的原因有很多，而不仅仅是搜索，正如广度优先 搜索 似乎暗示的那样，尽管许多(或大多数)没有做出这种区分并使用术语可互换。

我个人唯一一次真正使用“级别顺序遍历”是在谈论 in-, post- and pre-order traversals 时, 只是为了遵循相同的“...顺序遍历”格式。

---

对于一般图，“级别”的概念可能不是合式的(虽然您可以只是将其定义为与源节点的(最短)距离，我想)，因此，级别顺序遍历可能没有明确定义，但广度优先搜索仍然很有意义。

我在上面提到了一个“正确的”树(如果你想知道的话，它是一个完全由子分类组成的树)——这只是意味着“级别”的定义如你所期望的——每条边将级别增加一个.然而，人们可能能够稍微调整一下“级别”的定义(尽管这样做可能不会被广泛接受)，本质上允许边缘跳过级别(或者甚至在同一级别的节点之间有边缘)。例如:

level
  1          1
            / \
  2        /   3
          /   /
  3      2   4

因此层序遍历为1, 3, 2, 4,
而广度优先遍历将是 1, 2, 3, 4。