广度优先VS深度优先 [英] Breadth First Vs Depth First

问题描述

当遍历树/图什么是广度和深度第一之间的区别？任何编码或伪code例子将是巨大的。

When Traversing a Tree/Graph what is the difference between Breadth First and Depth first? Any coding or pseudocode examples would be great.

推荐答案

这两个术语两种不同的走了树的方式加以区分。

These two terms differentiate between two different ways of walking a tree.

这可能是最简单的只是表现出差异。考虑树：

It is probably easiest just to exhibit the difference. Consider the tree:

    A
   / \
  B   C
 /   / \
D   E   F

A 深度优先遍历将访问节点按此顺序

A depth first traversal would visit the nodes in this order

A, B, D, C, E, F

请注意，您在继续之前一路走的下一腿。

A 宽度优先遍历将访问节点按此顺序

A breadth first traversal would visit the node in this order

A, B, C, D, E, F

在这里，我们所有的工作方式横渡之前，每个级别下降。

Here we work all the way across each level before going down.

（需要注意的是，在穿越的订单有些含糊不清，我已经被骗维持阅读为了在树的每一层。在任何情况下，我能得到之前或C后，B，同样地我能拿到E之前或之后F.这可能会或可能没有关系，取决于你的应用程序...）

(Note that there is some ambiguity in the traversal orders, and I've cheated to maintain the "reading" order at each level of the tree. In either case I could get to B before or after C, and likewise I could get to E before or after F. This may or may not matter, depends on you application...)

这两种遍历都可以用伪code来实现：

Both kinds of traversal can be achieved with the pseudocode:

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

两个遍历订单之间的不同之处在于容器的选择。

• 对于深度优先使用堆栈。 （递归实现使用调用堆栈...）
• 对于广度优先使用队列。

• For depth first use a stack. (The recursive implementation uses the call-stack...)
• For breadth-first use a queue.

在递归实现看起来像

ProcessNode(Node)
   Work on the payload Node
   Foreach child of Node
      ProcessNode(child)
   /* Alternate time to work on the payload Node (see below) */

当你到达一个没有孩子的节点的递归结束，所以它是保证最后的 有限，非循环图。

The recursion ends when you reach a node that has no children, so it is guaranteed to end for finite, acyclic graphs.

在这一点上，我还是被骗了一点。随着一点点的小聪明，你也可以的工作在的这个顺序节点：

At this point, I've still cheated a little. With a little cleverness you can also work-on the nodes in this order:

D, B, E, F, C, A

这是深度优先，在这里我就不在每个节点上做的工作，直到我走回来了树的变化。我有不过的访问的途中更高节点下找到自己的孩子。

which is a variation of depth-first, where I don't do the work at each node until I'm walking back up the tree. I have however visited the higher nodes on the way down to find their children.

这遍历是递归执行相当自然的（使用备用时间线以上，而不是第一个工作行），而不是的太的硬盘，如果你使用一个明确的堆栈，但我会离开它作为一个练习。

This traversal is fairly natural in the recursive implementation (use the "Alternate time" line above instead of the first "Work" line), and not too hard if you use a explicit stack, but I'll leave it as an exercise.

这篇关于广度优先VS深度优先的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！