广度优先与深度优先

StackOverflow https://stackoverflow.com/questions/687731

题

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

有帮助吗？

解决方案

这两个条款之间作出区分两种不同的方式行走的一棵树。

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

    A
   / \
  B   C
 /   / \
D   E   F

一个 深度 第一个穿越将访问的节点，在这个顺序

A, B, D, C, E, F

注意你走的路 下 一条腿前移动。

一个 广度 第一个穿越将访问的节点，在这个顺序

A, B, C, D, E, F

在这里，我们所有的工作方式 跨越 每之前的水平在下降。

(注意，有一些模糊性的历的订单，并且我已经被骗了维持"阅读"以便在每个级别的树。在任何一种情况下，我可以得到以前B或C之后，同样我就可以得到电子之前或之后的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

这是一个变化的深度-第一,我没有做的工作，在每个节点，直到我走回了树。我有但是 访问 较高的节点的路上找到自己的儿童。

这一历是相当自然的递归的执行情况(使用"备用时间"的线路上，而不是第一个"工作"行)，而不 太 很难，如果你使用一个明确的堆，但我会把它作为一个运动。

其他提示

理解的条款：

这张照片应该给你这个想法有关的上下文的话 广度 和 深度 使用。

Understanding Breadth and Depth

深入一搜索：

Depth-First Search

  • 深先搜索算法的行为，如果它希望得到远 从起点，尽可能快地。

  • 它一般使用一个 Stack 记住它应当达到一条死胡同。

  • 要遵循的规则:推第一个顶点一到 Stack

    1. 如果可能，请访问相邻的未访问的顶点，标记它作为访问，并推动它在栈。
    2. 如果你可以不遵循规则1，然后，如果可能的话，弹出一个顶点关栈。
    3. 如果你不能遵照规则第1或第2条，你在做。

  • Java:

    public void searchDepthFirst() {
    // Begin at vertex 0 (A)
    vertexList[0].wasVisited = true;
    displayVertex(0);
    stack.push(0);
    while (!stack.isEmpty()) {
        int adjacentVertex = getAdjacentUnvisitedVertex(stack.peek());
        // If no such vertex
        if (adjacentVertex == -1) {
            stack.pop();
        } else {
            vertexList[adjacentVertex].wasVisited = true;
            // Do something
            stack.push(adjacentVertex);
        }
    }
    // Stack is empty, so we're done, reset flags
    for (int j = 0; j < nVerts; j++)
        vertexList[j].wasVisited = false;
}

  • 应用程序:深度第一次搜索，通常用于模拟游戏(和游戏-等情况下在真实的世界)。在一个典型的游戏，你可以选择几种可能的行动。每个选择都会导致进一步的选择，每个这导致进一步的选择，因此在成为一个不断扩大的树形图表的可能性。

广度优先的搜索：

Breadth-First Search

  • 广度优先搜索算法的喜欢保持尽可能靠近 到起点。
  • 这种搜索的一般实施使用 Queue.
  • 要遵循的规则:让开始的一个顶点目前的顶点
    1. 参观下一个未访问的顶点(如果有)的邻目前的顶点，标记它，并把它插进队列中。
    2. 如果你不能进行第1条，因为没有更多的未访问的顶点，删除一个顶点从排队(如果可能的话)，并使其目前的顶点。
    3. 如果你不能进行第2条，因为队列是空的，你完成。

  • Java:

    public void searchBreadthFirst() {
    vertexList[0].wasVisited = true;
    displayVertex(0);
    queue.insert(0);
    int v2;
    while (!queue.isEmpty()) {
        int v1 = queue.remove();
        // Until it has no unvisited neighbors, get one
        while ((v2 = getAdjUnvisitedVertex(v1)) != -1) {
            vertexList[v2].wasVisited = true;
            // Do something
            queue.insert(v2);
        }
    }
    // Queue is empty, so we're done, reset flags
    for (int j = 0; j < nVerts; j++) 
        vertexList[j].wasVisited = false;
}

  • 应用程序:广度优先搜索一下发现所有的顶点，是一个边远离起点，然后所有的顶点是两边走，等等。这是有用的，如果你试图找到的最短路径从开始的顶点到给予折点。

希望这应该够了解的广度和深度第一次搜索。进一步阅读，我将建议图章从一个良好的数据结构的书，由罗伯特*Lafore.

给定这个二叉树：

enter image description here

广度优先遍历：
从左到右遍历每个级别。

“我是 G，我的孩子是 D 和我，我的孙子是 B、E、H 和 K，他们的孙子是 A、C、F”

- Level 1: G 
- Level 2: D, I 
- Level 3: B, E, H, K 
- Level 4: A, C, F

Order Searched: G, D, I, B, E, H, K, A, C, F

深度优先遍历：
遍历并不是一次跨越整个级别。相反，遍历首先深入到树的深度（从根到叶）。然而，它比简单的上下要复杂一些。

有以下三种方法： 

1) PREORDER: ROOT, LEFT, RIGHT.
You need to think of this as a recursive process:  
Grab the Root. (G)  
Then Check the Left. (It's a tree)  
Grab the Root of the Left. (D)  
Then Check the Left of D. (It's a tree)  
Grab the Root of the Left (B)  
Then Check the Left of B. (A)  
Check the Right of B. (C, and it's a leaf node. Finish B tree. Continue D tree)  
Check the Right of D. (It's a tree)  
Grab the Root. (E)  
Check the Left of E. (Nothing)  
Check the Right of E. (F, Finish D Tree. Move back to G Tree)  
Check the Right of G. (It's a tree)  
Grab the Root of I Tree. (I)  
Check the Left. (H, it's a leaf.)  
Check the Right. (K, it's a leaf. Finish G tree)  
DONE: G, D, B, A, C, E, F, I, H, K  

2) INORDER: LEFT, ROOT, RIGHT
Where the root is "in" or between the left and right child node.  
Check the Left of the G Tree. (It's a D Tree)  
Check the Left of the D Tree. (It's a B Tree)  
Check the Left of the B Tree. (A)  
Check the Root of the B Tree (B)  
Check the Right of the B Tree (C, finished B Tree!)  
Check the Right of the D Tree (It's a E Tree)  
Check the Left of the E Tree. (Nothing)  
Check the Right of the E Tree. (F, it's a leaf. Finish E Tree. Finish D Tree)...  
Onwards until...   
DONE: A, B, C, D, E, F, G, H, I, K  

3) POSTORDER: 
LEFT, RIGHT, ROOT  
DONE: A, C, B, F, E, D, H, K, I, G

用法（又名，我们为什么关心）：
我真的很喜欢 Quora 对深度优先遍历方法及其常用方法的简单解释：
“按序遍历将打印值[按 BST（二叉搜索树）的顺序]”
“前序遍历用于创建[二叉搜索树]的副本。”
“后序遍历用于删除[二叉搜索树]。”
https://www.quora.com/What-is-the-use-of-pre-order-and-post-order-traversal-of-binary-trees-in-computing

我认为这将是有趣的方式，只有通过交换一些代码行会给你一个算法或其他写他们两个，所以你会看到你的dillema没有那么强，因为它似乎是在第一。

我个人很喜欢BFS的解释洪水的一道风景：低海拔地区将被淹没先，然后才在高海拔地区会跟随。如果你想象的景观高度为等值线，因为我们在地理书看，它很容易看到，BFS填充在同一时间同一等值线下的所有区域，只是因为这是物理学。因此，解释的高度作为距离或缩放成本给出了算法的一个相当直观的想法。

考虑到这一点，你可以很容易地适应广度背后的想法首先搜索很容易地找到最小生成树，最短路径，以及许多其他的最小化算法。

我没有看到DFS的任何直观的解释，但（仅约迷宫的标准之一，但它不是作为BFS一个和洪水一样强大），所以对我来说似乎BFS似乎关联与物理现象更好地描述以上，而DFS相关与理性选择系统更好dillema（即其移动，使上一盘棋，或走出去迷宫的人或电脑决定）。

所以，对我来说在其自然现象最好的传播模型（横移）在现实生活相匹配的谎言之间的区别。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top