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

问题描述

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

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 depth first traversal would visit the nodes in this order

A, B, D, C, E, F

请注意，在继续前进之前，您要一直向下一条腿.

Notice that you go all the way down one leg before moving on.

广度的第一次遍历会按照这个顺序访问节点

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，同样我可以在 F 之前或之后到达 E.这可能重要也可能无关紧要，取决于您的申请...)

(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...)

两种遍历都可以用伪代码实现:

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

两种遍历顺序的区别在于Container的选择.

The difference between the two traversal orders lies in the choice of Container.

• 对于深度优先，请使用堆栈.(递归实现使用调用堆栈...)
• 对于广度优先，请使用队列.

• 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.

这种遍历在递归实现中相当自然(使用上面的Alternate time"行而不是第一个Work"行)，如果使用显式堆栈，则不会太，但是我将把它留作练习.

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.

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