首页 文章

广度优先搜索：检查访问状态的时间

提问于
浏览 次
8

在有向图的广度优先搜索中（可能的循环），当节点出列时，其尚未被访问的所有子节点都被排队，并且该过程继续，直到该队列为空 .

有一次，我以相反的方式实现它，其中所有节点的子节点都被排队，并且当节点出列时检查访问状态 . 如果之前已访问过出队的节点，则将其丢弃，并且该过程继续到队列中的下一个节点 .

但结果是错误的 . Wikipedia也说

深度优先搜索......非递归实现类似于广度优先搜索，但在两个方面与它不同：它使用堆栈而不是队列，并且延迟检查是否已发现顶点直到从堆栈弹出顶点而不是在推顶点之前进行此检查 .

但是，我无法理解究竟是什么区别 . 为什么在弹出项目时首先进行深度搜索检查，并且在排队之前必须检查广度优先搜索？

algorithm graph language-agnostic

2 回答

  • 2

    DFS

    假设你有一个图表：

    A---B---E
 |   |
 |   |
 C---D

    你从A搜索DFS .

    如果使用深度优先搜索（假设孩子的某种顺序），你会期望它搜索节点A，B，D，C，E .

    但是，如果在将节点放置到堆栈之前将节点标记为已访问，那么您将访问A，B，D，E，C，因为当我们检查A时，C被标记为已访问 .

    在某些您只想访问所有连接节点的应用程序中，这是完全有效的事情，但从技术上讲，它不是深度优先搜索 .

    BFS

    在广度优先搜索中，您可以在推送到队列之前或之后将节点标记为已访问 . 但是，之前检查更有效，因为队列中没有大量重复节点 .

    我不明白为什么你的BFS代码在这种情况下失败了，也许如果你发布代码它会变得更清楚？

    回复于
  • 9

    DFS在出列时检查是否已访问节点，因为它可能已在“更深”级别访问过 . 例如：

    A--B--C--E
|     |
-------

    如果我们从A开始，那么B和C将被放入堆栈;假设我们将它们放在堆栈上，因此B将首先被处理 . 当B现在被处理时，我们想要下到C，最后到E，如果我们从A中发现它时将C标记为已访问则不会发生 . 现在我们从B开始，我们找到尚未访问的C并放入它第二次在堆栈上 . 在我们完成处理E之后，需要忽略堆栈上的所有C条目，访问的标记将为我们处理 .

    正如@PeterdeRivaz所说，对于BFS来说，这不是正确性，而是效率，无论我们检查节点是否在入队或出列时被访问过 .

    回复于

相关问题