广度优先与深度优先

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”行），如果您使用显式堆栈，则不会太困难，但我会将其作为练习。

Answer 2

理解术语：

这张图片应该能让您了解使用“宽度”和“深度”这两个词的上下文。

---

深度优先搜索：

• 深度优先搜索算法的行为就好像它想要尽可能远
  尽可能快地从起点开始。

• 它通常使用一个Stack来记住当它到达死胡同时应该去哪里。

• 遵循的规则：将第一个顶点 A 推入 Stack

  1. 如果可能，访问相邻的未访问顶点，将其标记为已访问，然后将其压入堆栈。
  2. 如果您无法遵循规则 1，那么如果可能的话，从堆栈中弹出一个顶点。
  3. 如果您无法遵守规则 1 或规则 2，那么您就完蛋了。

• Java代码：

  public void searchDepthFirst() { 
        // 从顶点 0 (A) 开始 
        vertexList[0].wasVisited = true; 
        显示顶点(0); 
        堆栈.推(0); 
        while (!stack.isEmpty()) { 
            int相邻顶点 = getAdjacentUnvisitedVertex(stack.peek()); 
            // 如果没有这样的顶点 
            if (相邻顶点 == -1) { 
                堆栈.pop(); 
            } 别的 { 
                vertexList[adjacentVertex].wasVisited = true; 
                // 做一点事 
                stack.push(adjacentVertex); 
            } 
        } 
        // 堆栈是空的，所以我们完成了，重置标志 
        for (int j = 0; j < nVerts; j++) 
            vertexList[j].wasVisited = false; 
    } 
    

• 应用：深度优先搜索通常用于模拟游戏（以及现实世界中类似游戏的情况）。 在典型的游戏中，您可以选择几种可能的操作之一。 每个选择都会导致进一步的选择，每个选择都会导致进一步的选择，依此类推，形成一个不断扩大的树形可能性图。

---

广度优先搜索：

• 广度优先搜索算法喜欢保持尽可能接近
  到起点。
• 这种搜索通常使用队列来实现。
• 遵循的规则：使起始顶点 A 成为当前顶点
  1. 访问与当前顶点相邻的下一个未访问顶点（如果有），对其进行标记，然后将其插入队列。
  2. 如果由于不再有未访问的顶点而无法执行规则 1，请从队列中删除一个顶点（如果可能）并将其设为当前顶点。
  3. 如果由于队列为空而无法执行规则 2，那么您就完成了。

• Java代码：

  public void searchBreadthFirst() { 
        vertexList[0].wasVisited = true; 
        显示顶点(0); 
        队列.插入(0); 
        整数v2； 
        while (!queue.isEmpty()) { 
            int v1 = 队列.remove(); 
            // 直到没有未访问过的邻居为止，获取一个 
            while ((v2 = getAdjUnvisitedVertex(v1)) != -1) { 
                vertexList[v2].wasVisited = true; 
                // 做一点事 
                队列.插入(v2); 
            } 
        } 
        // 队列为空，所以我们完成了，重置标志 
        for (int j = 0; j < nVerts; j++)  
            vertexList[j].wasVisited = false; 
    } 
    

• 应用：广度优先搜索首先查找满足以下条件的所有顶点：距起点一条边，然后是距起点两条边的所有顶点，依此类推。 如果您试图找到从起始顶点到给定顶点的最短路径，这非常有用。

希望这足以理解广度优先和深度优先搜索。 为了进一步阅读，我推荐 Robert Lafore 所著的一本优秀的数据结构书中的“图表”章节。

Answer 3

给定这个二叉树：

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

“我是 G，我的孩子是 D 和 I，我的孙子是 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

< strong>深度优先遍历：
遍历并不是一次跨越整个关卡。 相反，遍历首先深入到树的深度（从根到叶）。 但是，它比简单的向上和向下要复杂一些。

共有三种方法：

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

Answer 4

我认为以一种方式编写它们会很有趣，只需切换几行代码就会给你一个算法或另一个算法，这样你就会发现你的困境并不像一开始看起来那么强烈。

我个人喜欢将 BFS 解释为淹没景观：低海拔地区将首先被淹没，然后才是高海拔地区。 如果你把景观高度想象成我们在地理书上看到的等值线，很容易看出 BFS 同时填充了同一条等值线下的所有区域，就像物理学中的情况一样。 因此，将高度解释为距离或缩放成本给出了算法的非常直观的想法。

考虑到这一点，您可以轻松地采用广度优先搜索背后的思想来轻松找到最小生成树、最短路径以及许多其他最小化算法。

我还没有看到 DFS 的任何直观解释（只有关于迷宫的标准解释，但它不如 BFS 和洪水那么强大），所以对我来说，BFS 似乎与上述物理现象有更好的相关性，而DFS 与理性系统上的选择困境（即人或计算机决定在国际象棋游戏中采取哪一步或走出迷宫）有更好的相关性。

因此，对我来说，两者之间的区别在于哪种自然现象最符合其在现实生活中的传播模型（横向）。