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

Question

33

我不需要代码，只需要解释。我的教材上写道：

层序遍历：在处理任何一级别 i+1 的节点之前，处理每个级别为 i 的节点。

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

- munchschair

2

据我所知，它们没有区别；你可以互换使用“广度优先”和“层序遍历”。 - rici

这个。每个人似乎都单独定义它们，但它们实际上做的是同样的事情。 - munchschair

4个回答

2

什么是广度优先搜索和层序遍历之间的区别？

定义：“有序树的级别顺序是该树标准平面绘图的自上而下、从左到右顺序中顶点的列表”。

请注意，当我们讨论层次顺序时，我们仅谈论树，而不是一般的图。

而且我们可以更具体地说，我们正在讨论有根树。

定义：“有根树是一个带有指定顶点（称为根）的树。每条边被认为是从根指向的。因此，有根树是一个有向树，使得根具有入度=0（因此没有传入的边）”。

重要的是要进行区分，因为正是这个属性允许对树进行递归实现。

此外，层序遍历在图形结构中没有意义（树是图形的一种特定类型（无环且连通））。

因此，对于图形结构，我们使用BFS，并且我们用于树的BFS被称为“层序遍历”（因为由于我们正在讨论有根树，所以级别确实有意义。而在图形中，由于缺少根，它们将没有意义）。

结论：层序遍历是特定图形结构（即有根树）的广度优先搜索。

- Kejsi Struga

1

我们在树中使用层次遍历，因为树中没有循环，一旦访问了一个节点，它就不会再被访问了。但是在图中情况并非如此。图可以是循环的。如果图是循环的，按照层次遍历的规则，如果访问了一个节点，它不会检查是否已经访问过，并且会无限次地遍历同一节点。由于循环，程序将继续遍历。因此，在图中我们使用BFS或DFS。

- SUMIT LOHAN

1

我猜根据这种解释，层序遍历意味着在实现中使用了特定类型的逻辑（不检查节点是否已被访问），而BFS / DFS则意味着在实现中使用了不同类型的基础逻辑（实际上检查节点是否已被访问）。正确吗？ - XDS

1

一般来说，遍历是一种访问数据结构中所有元素仅一次的技术。获取、修改、检查树中所有节点数据的过程称为树遍历。

搜索意味着查找一个项目。它并不意味着你要访问所有节点。假设你正在寻找第一个值小于10的节点，一旦找到10，你就退出搜索。

- Yilmaz

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bernhard Barker · Accepted Answer

对于一个“正确”的树（见下文），至少按大多数定义，它是相同的。例如，像维基百科中所述：

广度优先

另见：广度优先搜索

还可以按层次顺序遍历树...

... 广度优先（层次顺序）遍历 ...

好吧，至少按照大多数定义，“层次顺序遍历”和广度优先遍历是相同的。有很多理由可以遍历某些东西，这不仅仅是为了搜索，就像广度优先搜索所暗示的那样，尽管许多人（或多或少）并没有区分并且互换使用这些术语。

唯一我个人真正使用“层次顺序遍历”的时间是在谈论前序、后序和中序遍历时，只是为了遵循相同的“...-order遍历”格式。

对于一般图形，'级别'的概念可能不是明确的（尽管你可以将其定义为源节点的（最短）距离，我想），因此“层次顺序遍历”可能没有明确定义，但广度优先搜索仍然非常有意义。

我上面提到了一个“正确”的树（这是一种完全虚构的子分类，如果你在疑惑的话）- 这意味着“级别”被定义为你所期望的方式-每个边增加一个级别。然而，人们可能会稍微玩弄“级别”的定义（尽管这样做可能不被广泛接受），从本质上允许边跨越级别（甚至在同一级别的节点之间具有边）。例如：

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

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