如何在没有箭头的图形上进行深度优先搜索？

Question

我在做作业时遇到了这个问题，我想知道答案是否是4，3，2，1，5，9，9，13，7，6，10，15，11，14，8，12，16，

我知道了

从该图中开始，它基于广度优先搜索，我认为可以在其上应用深度优先搜索，对吗？

Answer 1

如果您使用深度优先搜索来探索图，并且每个顶点的边都存储在升序的邻接表中，那么您探索的下一个顶点将始终是未探索的邻居中最小的顶点。

[从顶点4开始时，顶点4的边缘的邻接列表表示为[3，8]。假设深度优先搜索通过探索存储在邻接表中的第一个顶点来发现下一个顶点，则顶点3将是找到的下一个顶点。

在其余问题中应用此问题，我们可以看到，当遇到具有邻接表[1，6，9]的顶点5时，您已经正确地跳过了顶点1，因为它已经被探索了。但是，您从此处错误地继续了顶点9，而不是继续了顶点6。

具有这些约束的正确的深度优先搜索遍历为：4-3-2-1-5-6-7-8-12-11-14-10-9-13-15-16

修复此错误后，在这种情况下，您可以通过深度优先搜索解决您的问题。如果仍然需要更多练习，请尝试从顶点4以外的其他顶点开始尝试。祝你好运。