graph - 我试图理解深度优先搜索。不知道我是否正确

Question

http://i.stack.imgur.com/sEJKz.png

该图显示了一个图表。这是正确的深度优先遍历吗？还是我的想法完全错误？我对dfs的理解给出了一个起点，你看看所有相邻的节点。然后，任意选择一个并递归地“访问”该节点。从 v 开始，我选择了节点 2 进行下一步。从 1 到 8 的数字表示路径。

编辑：我似乎把数字 2 和 3 弄混了！他们应该被交换。

图 2：http: //i.stack.imgur.com/KdWl6.png

Answer 1

您显示的是正确的可能 DFS 搜索顺序。正如您所说，DFS 递归访问，标记它已经访问过的节点。当它到达无法递归到未访问节点的点时，它将回溯，直到存在这样的点或搜索终止，因为所有节点都被标记为已访问。

在您的情况下，它访问 1、2 和 3。在 3 处，它回溯到 2，然后继续到 4、5、6、7、8。然后它会回溯，但是所有节点都被访问，因此搜索以这个终止参观顺序。

在这种情况下，标记为 3 的节点也可能是 2 或 8。例如，DFS 可能已经消失（使用图中的标签）：1、2、4、5、6、7、8，回溯到 2， 3、终止。