广度优先vs深度优先

Question

遍历树/图时，广度优先和深度优先有什么区别？任何编码或伪代码示例都很好。

Answer 1

这两个术语区分了步行树的两种不同方式。

展示差异可能是最容易的。考虑这棵树：

    A

   / \

  B   C

 /   / \

D   E   F

一个深度优先遍历将访问节点顺序

A, B, D, C, E, F

请注意，在继续前进之前，您要完全沿着一条腿向下移动。

一个广度优先遍历将访问节点顺序

A, B, C, D, E, F

在这里，我们一直深入到每个级别，然后再进行下去。

（请注意，遍历顺序有些歧义，我作弊要在树的每个级别上保持“读取”顺序。无论哪种情况，我都可以在C之前或之后到达B，同样，我可以到达E在F之前或之后。这可能会或可能不会重要，取决于您的应用程序...）

两种遍历都可以通过伪代码实现：

Store the root node in Container

While (there are nodes in Container)

   N = Get the "next" node from Container

   Store all the children of N in Container

   Do some work on N

两种遍历顺序之间的差异在于对的选择Container。

对于深度，请先使用堆栈。（递归实现使用调用堆栈...）

对于广度优先，请使用队列。

递归实现看起来像

ProcessNode(Node)

   Work on the payload Node

   Foreach child of Node

      ProcessNode(child)

   /* Alternate time to work on the payload Node (see below) */

当您到达没有子节点的节点时，递归结束，因此对于有限的非循环图，可以保证递归结束。

在这一点上，我还是有点作弊。随着一点点的小聪明，你也可以工作在这个秩序中的节点：

D, B, E, F, C, A

这是深度优先的一种变体，在这种情况下，直到我向后走到树上之前，我不会在每个节点上进行工作。但是，我在去的途中参观了较高的节点以找到他们的孩子。

在递归实现中，这种遍历是很自然的（使用上面的“ Alternate time”行而不是第一条“ Work”行），并且如果您使用显式堆栈也不会太难，但是我将其保留为练习。