广度优先与深度优先搜索

Question

广度优先与深度优先搜索

algorithmrecursiondepth-first-searchbreadth-first-searchtree-traversal

213

遍历树/图时，广度优先和深度优先的区别是什么？提供任何编码或伪代码示例都可以。

- Ted Smith

6

你是否查看了维基百科的深度优先搜索和广度优先搜索页面？这些页面上有代码示例以及大量精美图片。 - rmeador

1

我也有过那个想法，但是给出的例子比维基百科上找到的例子稍微好一些... - jonnybazookatone

1

请查看此可视化示例。虽然我想把它作为回答发布，但由于它只是一个链接，它可能会被投票否决，所以我发了一条评论。 - Guy Coder

4个回答

127

术语理解:

这张图片应该让你了解词语广度和深度的使用背景。

深度优先搜索:

深度优先搜索算法会尽可能快地远离起点。
它通常使用一个栈来记住在到达死路时应该去哪里。
遵循的规则:
1. 将第一个顶点A推入栈。
2. 如果可能，访问相邻未访问的顶点，标记为已访问并将其推入栈中。
3. 如果无法执行规则1，则如果可能，从堆栈中弹出一个顶点。
4. 如果无法执行规则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;
}

应用场景：深度优先搜索经常用于模拟游戏（以及现实世界中类似游戏的情况）。在一个典型的游戏中，你可以选择几个可能的行动。每个选择都会导致进一步的选择，每个进一步的选择都会导致更多的选择，以此类推形成一个越来越庞大的树状图。

广度优先搜索:

广度优先搜索算法喜欢尽可能地接近起始点。
这种搜索通常使用队列进行实现。
遵循以下规则：将起点 A 设为当前顶点
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;
}

应用：广度优先搜索首先找到所有距起点一个边的顶点，然后找到所有距离为二个边的顶点，以此类推。如果你想要找到从起始顶点到给定顶点的最短路径，那么这就非常有用。

希望以上内容足够理解广度优先搜索和深度优先搜索。如需进一步阅读，我建议阅读Robert Lafore撰写的相关数据结构书籍中的“图”章节。

- Yogesh Umesh Vaity

10

如果我有十个额外的投票权，我会这样做。 - Soner from The Ottoman Empire

@snr 你可以授予一份赏金 ;) - Snow

2

谢谢@Snow，很高兴你们觉得我的回答有用。 - Yogesh Umesh Vaity

1

@YogeshUmeshVaity 很棒的回答——这是一个解释得非常好的顶级StackOverflow/StackExchange回复的典型例子。id="dmid://uu745gurulevel1622917502" - dreftymac

1

@mcvkr，不用担心。我很荣幸你认为这个答案值得奖励赏金。 - Yogesh Umesh Vaity

显示剩余3条评论

6

给定这个二叉树：

广度优先遍历：
从左到右遍历每一层。

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

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

有三种方法：

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 上这篇简单的解释，它介绍了深度优先遍历方法及其常见用途：
“中序遍历（In-Order Traversal）将[二叉搜索树]中的值按顺序打印出来。”
“前序遍历（Pre-order traversal）用于创建[二叉搜索树]的副本。”
“后序遍历（Postorder traversal）用于删除[二叉搜索树]。”
https://www.quora.com/What-is-the-use-of-pre-order-and-post-order-traversal-of-binary-trees-in-computing

- msyinmei

2

我认为有趣的是，通过仅仅切换代码中的一些行，就可以得到另一个算法，这样你就会发现你的困境并不像一开始看起来那么严重。

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

有了这个想法，你可以轻松地将广度优先搜索的思想适应于查找最小生成树、最短路径和许多其他最小化算法。

我还没有看到DFS的直观解释（只有关于迷宫的标准解释，但它不如BFS强大且具有洪水的特性），因此对我来说，BFS似乎更好地与上述物理现象相匹配，而DFS则更好地与理性系统（即人类或计算机在国际象棋游戏或走出迷宫时做出决策）的选择困境相匹配。

因此，对我来说，它们之间的差异在于哪种自然现象最能匹配它们在现实生活中的传播模型（遍历）。

- user5193682

1

你可以使用类似的算法来实现它们，只需在DFS中使用堆栈，在BFS中使用队列。 BFS的问题在于需要跟踪到目前为止看到的所有节点。在物理学中，DFS是这样的...我想象着替代宇宙，你想要一个有生命的宇宙，所有的根节点的孩子都是不同的大爆炸，你一直走到宇宙死亡，没有生命？你回到最后的分叉点，尝试另一个转弯，直到所有的都耗尽了，然后你去下一个大爆炸，为新的宇宙设置新的物理定律。超级直观。一个好的问题是找到马在棋盘上的路线。 - juanmf

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dmckee · Accepted Answer

这两个术语区分了遍历树的两种不同方式。

最好是直接展示它们之间的差异。考虑下面这棵树：

    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

两种遍历顺序的区别在于所选择的容器不同。

对于深度优先，使用堆栈。（递归实现使用调用栈...）
对于广度优先，使用队列。

递归实现如下：

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

这是一种深度优先的变体，其中我在回溯树之前不会对每个节点执行操作。然而，在下行过程中，我已经访问了更高的节点以查找它们的子节点。

如果使用递归实现，这种遍历方式相当自然（请使用上面的“替代时间”行，而不是第一个“工作”行），如果使用显式堆栈，也不会太难，但我将把它留作练习。