广度优先Vs深度优先

这两个术语区分了在树上行走的两种不同方式。

最简单的方法可能就是展示这种差异。想想这棵树:

    A
/ \
B   C
/   / \
D   E   F

深度第一次遍历将按此顺序访问节点

A, B, D, C, E, F

请注意，在继续前进之前，你一直在走一条腿下来。

宽度第一次遍历将按此顺序访问节点

A, B, C, D, E, F

在这里，我们一直工作在每一层之前下降。

(注意遍历顺序有一些不明确的地方，我在树的每一层都维护了“读取”顺序。在任何一种情况下，我都可以在C之前或之后到达B，同样地，我也可以在f之前或之后到达E，这可能有关系，也可能没有关系，这取决于你的应用……)

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

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的选择。

• 对于深度优先使用堆栈。(递归实现使用call-stack…)
• 对于广度优先使用队列。

递归实现看起来像

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

理解术语:

这张图应该会让你对使用宽度和深度这两个词的上下文有一个概念。

深度优先搜索:

深度优先搜索算法的行为就好像它想要到达尽可能远的地方

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

• 将第一个顶点A推到Stack
  1. 如果可能，访问一个相邻的未访问顶点，将其标记为已访问顶点，并将其推入堆栈。
  2. 如果你不能遵循规则1，那么，如果可能的话，从堆栈中弹出一个顶点。
  3. 如果你不能遵守规则1或规则2，你就完了。
  李< / ol > < / >
  4. < p > 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;
     }
     

  5. Applications: Depth-first searches are often used in simulations of games (and game-like situations in the real world). In a typical game you can choose one of several possible actions. Each choice leads to further choices, each of which leads to further choices, and so on into an ever-expanding tree-shaped graph of possibilities.

Breadth-First Search:

• The breadth-first search algorithm likes to stay as close as possible to the starting point.
• This kind of search is generally implemented using a Queue.
• Rules to follow: Make starting Vertex A the current vertex
  1. Visit the next unvisited vertex (if there is one) that’s adjacent to the current vertex, mark it, and insert it into the queue.
  2. If you can’t carry out Rule 1 because there are no more unvisited vertices, remove a vertex from the queue (if possible) and make it the current vertex.
  3. If you can’t carry out Rule 2 because the queue is empty, you’re done.

• Java code:

  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: Breadth-first search first finds all the vertices that are one edge away from the starting point, then all the vertices that are two edges away, and so on. This is useful if you’re trying to find the shortest path from the starting vertex to a given vertex.

Hopefully that should be enough for understanding the Breadth-First and Depth-First searches. For further reading I would recommend the Graphs chapter from an excellent data structures book by Robert Lafore.

我认为，用一种只需要切换几行代码就能得到一种或另一种算法的方式来编写它们会很有趣，这样你就会发现，你的困境并没有一开始看起来那么严重。

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

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

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

所以，对我来说，两者之间的区别在于，在现实生活中，哪种自然现象最符合它们的传播模式(横向)。

给定这个二叉树:

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