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

Question

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

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

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

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

Answer 1

深度优先搜索主要用于查找图中两个节点之间的路径。您的示例图是 disconnected，即图中存在两个节点，因此图中没有路径将这些节点作为端点。

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