depth-first-search - 使用深度优先搜索正确遍历无向图？

Question

我有一个无向图，我需要使用深度优先搜索来遍历它。

下面的excel图表在标记列中显示了遍历后每个节点都被标记了，edgeTo列显示了是哪个节点把我们带到了那个节点。例如，我们从节点 5 到节点 1，我们从节点 7 到节点 2，等等。

我的问题是节点 6 和 8，因为它们与主图分开，我该如何正确遍历它？我的猜测是我从 6 开始到 8，但由于那时已经访问了 6，所以我不会从 8 回到 6。因此第 6 行在 edgeTo 列中留空。

我对么？我的图表正确吗？

Answer 1

深度优先搜索基本上用于查找图中两个节点之间的路径。您的示例图已断开连接，即您的图中存在两个节点，因此您的图中没有路径将这些节点作为端点。

6 和 8 显然是属于不同子图的节点，因此您找不到 0 和 8 之间的路径，并且 DFS 将返回IMPOSSIBLE或No path found。除此之外，您的图表是正确的。