我正在用Java编写程序，我必须实现三种搜索算法，其中三种是深度优先的图搜索算法 . 我的程序遍历由邻接矩阵在内部表示的连通图，并使用每个算法的前沿和探索集 .
边界存储扩展父节点的未探测子节点，探索集存储实际已扩展的节点 . 探索集的目的是避免重复，从而避免无限循环 .
我的前沿是使用链接的阻塞deque和我使用链接哈希集的探索集实现的 .
然而，在测试该算法实现的初始版本时，我注意到仍然存在少量重复，特别是当目标节点不存在并且算法肯定必须访问图中的每个节点时 . 最终我意识到这是因为当一个节点被扩展时，它的所有子节点都被添加到边界，但只探索其中一个节点 . 因为图是连接的，所以节点可能存在其他路径，这可能导致节点在被扩展之前被多次遇到并因此被添加到被探索的集合中 .
这引出了我的问题，我修复它吗？
深度优先搜索应该首先探索从图形形成的树的一侧然后回溯，这意味着即使它在树的一侧遇到不太理想的目标节点，它应该返回而不是（更优化） ）一个以前遇到但尚未探索过的人 .
但是，如果我为了避免重复而实现一个被探索的集合，那么在某些情况下我允许它们似乎是矛盾的 .
我认为真正的错误可能在于缺乏对算法的透彻理解，我真诚地希望得到一些帮助，在此先感谢 .
1 回答
通常称为深度优先搜索的算法不需要"frontier"，就像你所说的那样 . 然而，这个概念用于A *图搜索（在那里通常称为"open set"） .
对于标准深度优先搜索，您只需要一堆节点：在堆栈上推送初始节点，然后在每个步骤中从堆栈中弹出一个节点，检查它并将其所有邻居（*）推送到堆栈顶部 . 然后，重复一遍 .
（*）记得将您在堆栈上推送的所有节点标记为已访问（我相信您在问题中称之为“探索集”）并且不要推送已经访问过的节点 .
通过使用堆栈，您可以避免描述的问题 .
如果您确实想要维护该前沿/开放集，请确保它永远不会包含重复项：使用不允许重复的数据结构（例如
set） .（旁注：如果您的图形节点具有自然编号，并且您希望DFS访问大多数注释，那么您也可以使用
array/vector作为已探索的集/闭集 . ）