广度优先与深度优先

4 回答

• 251

  这两个术语区分了两种不同的树木行走方式 .

  展示差异可能是最简单的 . 考虑树：

  A
     / \
    B   C
   /   / \
  D   E   F
  

  depth 首次遍历将按此顺序访问节点

  A, B, D, C, E, F
  

  请注意，在继续前行之前，你要一路走一条腿 .

  breadth 首次遍历将按此顺序访问节点

  A, B, C, D, E, F
  

  在这里，我们一路工作 across 每个级别在下降之前 .

  （请注意，遍历顺序存在一些模糊性，我在树的每个级别都要保持“阅读”顺序 . 在任何一种情况下，我都可以在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 的选择 .

  • 对于 depth first 使用堆栈 . （递归实现使用调用堆栈......）

  • 对于 breadth-first 使用队列 .

  ---

  递归实现看起来像

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

  回复于 2024-04-28T18:59:39+08:00
• 2

  了解条款：

  这张图片应该让您了解使用广度和深度这个词的上下文 .

  

  ---

  深度优先搜索：

  

  • 深度优先搜索算法就好像它想要尽可能快地远离起点 .

  • 它通常使用 Stack 来记住它到达死胡同时应该去的地方 .

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

  • 如果可能，访问相邻的未访问顶点，将其标记为已访问，并将其推入堆栈 .

  • 如果您不能遵循规则1，那么，如果可能，从堆栈中弹出一个顶点 .

  • 如果您不能遵守规则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;
  }
  

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

  ---

  广度优先搜索：

  

  • 广度优先搜索算法喜欢尽可能接近起点 .

  • 这种搜索通常使用 Queue 实现 .

  • 要遵循的规则：将顶点A作为当前顶点

  • 访问与当前顶点相邻的下一个未访问的顶点（如果有的顶点），标记它并将其插入队列 .

  • 如果由于没有更多未访问的顶点而无法执行规则1，请从队列中删除顶点（如果可能）并使其成为当前顶点 .

  • 如果因为队列为空而无法执行规则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;
  }
  

  • Applications：广度优先搜索首先查找距离起点一个边的所有顶点，然后查找距离两个边的所有顶点，依此类推 . 如果您尝试找到从起始顶点到给定顶点的最短路径，这将非常有用 .

  希望这应该足以理解广度优先和深度优先搜索 . 为了进一步阅读，我将推荐Robert Lafore出色的数据结构书中的Graphs章节 .

  回复于 2024-04-28T18:59:39+08:00
• 2

  我认为以一种方式编写它们会很有意思，只有通过切换一些代码行才会给你一个算法或另一个算法，这样你就会发现你的dillema并不像看起来那么强大 . .

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

  考虑到这一点，您可以轻松地将广度优先搜索背后的想法进行调整轻松找到最小生成树，最短路径，以及许多其他最小化算法 .

  我还没有看到对DFS的任何直观解释（只有关于迷宫的标准解释，但它不像BFS那样强大并且泛滥），所以对我而言，似乎BFS似乎与如上所述的物理现象更好地相关，而DFS与理性系统上的选择dillema（即人或计算机决定在国际象棋比赛中进行哪些移动或走出迷宫）的关系更好 .

  所以，对我而言，现实生活中哪种自然现象最能与其传播模型（横向）相匹配的谎言之间存在差异 .

  回复于 2024-04-28T18:59:39+08:00
• 60

  鉴于这个二叉树：

  

  Breadth First Traversal:
  Traverse across each level from left to right.

  “我是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
  

  Depth First Traversal:
  Traversal is not done ACROSS entire levels at a time. Instead, traversal dives into the DEPTH (from root to leaf) of the tree first. However, it's a bit more complex than simply up and down.

  有三种方法：

  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
  

  Usage (aka, why do we care):
  我非常喜欢这个简单的Quora解释深度优先遍历方法以及它们如何被常用：
  "In-Order Traversal will print values [in order for the BST (binary search tree)]"
  "Pre-order traversal is used to create a copy of the [binary search tree]."
  "Postorder traversal is used to delete the [binary search tree]."
  https://www.quora.com/What-is-the-use-of-pre-order-and-post-order-traversal-of-binary-trees-in-computing

  回复于 2024-04-28T18:59:39+08:00