广度优先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 ContainerWhile (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”行），并且如果您使用显式堆栈也不会太难，但是我将其保留为练习。