java 深度优先搜索和广度优先搜索理解

Depth First Search and Breadth First Search Understanding

提问by Growler

I'm making Tetris as a fun side project (not homework) and would like to implement AI so the computer can play itself. The way I've heard to do it is use BFS to search through for available places, then create an aggregate score of the most sensible drop location...

我正在将俄罗斯方块作为一个有趣的副项目（不是家庭作业），并希望实现人工智能，以便计算机可以自己玩。我听说这样做的方法是使用 BFS 搜索可用的位置，然后创建最合理的放置位置的总分......

But I'm having trouble understanding the BFS and DFS algorithms. The way I learn best is by drawing it out... are my drawings correct?

但是我在理解 BFS 和 DFS 算法时遇到了麻烦。我最好的学习方法是把它画出来……我的画正确吗？

---

---

Thanks!

谢谢！

采纳答案by Vitor De Mario

The end result of your traversals is correct, you're pretty close. However, you're a little bit off in the details.

您遍历的最终结果是正确的，您非常接近。然而，你在细节上有点偏离。

In the depth first search, you will pop a node, mark it as visited and stack its unvisited children. In that order. The order may seem irrelevant for a tree, but if you had a graph with cycles, you could fall in an infinite loop, but this is another discussion.

在深度优先搜索中，您将弹出一个节点，将其标记为已访问并堆叠其未访问的子节点。以该顺序。顺序对于树来说似乎无关紧要，但是如果您有一个带有循环的图，您可能会陷入无限循环，但这是另一个讨论。

Given the baseline of the algorithm, after you push the root node into the stack, you will start your first iteration, immediately popping A. It will not remain on the stack until the end of the algorithm. You'll pop A, stack D, C and B all at once (or B, C and D, you can do it left to right or right to left, it's your choice) and mark A as visited. Right now, your stack has D in the bottom, C in the middle and B on top.

给定算法的基线，在你将根节点入栈后，你将开始你的第一次迭代，立即弹出 A。它不会留在栈上，直到算法结束。您将一次性弹出 A、堆栈 D、C 和 B（或 B、C 和 D，您可以从左到右或从右到左，这是您的选择）并将 A 标记为已访问。现在，你的筹码堆底部有 D，中间有 C，顶部有 B。

The next node popped is B. You'll push F and E into the stack (I'll keep the order the same as yours), marking B as visited. The stack has, from top to bottom, E F C D. Next, E is popped, no new nodes are added and E is marked as visited. The loop will continue, doing the same to F, C and D. The final order is A B E F C D.

弹出的下一个节点是 B。您将 F 和 E 压入堆栈（我将保持与您相同的顺序），将 B 标记为已访问。堆栈从上到下具有 EFC D。接下来，弹出 E，不添加新节点，并将 E 标记为已访问。循环将继续，对 F、C 和 D 执行相同的操作。最终顺序是 ABEFC D。

I'll try to rewrite the algorithm in a similar way to yours:

我将尝试以与您类似的方式重写算法：

Push root into stack
Loop until stack is empty
    Pop node N on top of stack
    Mark N as visited
    For each children M of N
        If M has not been visited (M.visited() == false)
            Push M on top of stack

I won't go into details for the breadth first search, the algorithm is exactly the same. The difference is in the data structure and how it behaves. A queue is FIFO (First In First Out) and, because of that, you will visit all the nodes in the same level before you start visiting the nodes in the inferior levels.

广度优先搜索的细节我就不赘述了，算法完全一样。区别在于数据结构及其行为方式。队列是 FIFO（先进先出），因此，在开始访问较低级别的节点之前，您将访问同一级别的所有节点。

回答by wazy

First of all I believe your traversals seem okay (from a quick overview). I am going to give you some useful links below.

首先，我相信您的遍历似乎没问题（从快速概述来看）。我将在下面为您提供一些有用的链接。

I've found some decent videos on youtube about this before but here is one (not the best I've seen) that covers it http://www.youtube.com/watch?v=eXaaYoTKBlE. If you are doing it for fun make two versions, one with DFS and one with BFS and benchmark them to observe the difference. Also download the graph searcher and any other tools you find useful from http://www.aispace.org/downloads.shtmlif you want to trace some for better understanding. And last but not least a stackoverflow question on DFS and BFS http://www.stackoverflow.com/questions/687731/

我之前在 youtube 上找到了一些关于这个的不错的视频，但这里有一个（不是我见过的最好的），涵盖了它http://www.youtube.com/watch?v=eXaaYoTKBlE。如果您是为了好玩，请制作两个版本，一个使用 DFS，一个使用 BFS，然后对它们进行基准测试以观察差异。如果您想跟踪一些以便更好地理解，还可以从http://www.aispace.org/downloads.shtml下载图形搜索器和您认为有用的任何其他工具。最后但并非最不重要的一个关于 DFS 和 BFS 的 stackoverflow 问题http://www.stackoverflow.com/questions/687731/