断开连接图上的 DFS

Question

DFS(G,v) 对于断开的图的表现如何？

假设一个图有 3 个连通分量，并且 DFS 应用于这 3 个连通分量之一，那么我们是访问每个组件还是仅访问其顶点 DFS 应用的组件。

意思是这样说对吗

具有许多组件的图上的 DFS 仅涵盖 1 个组件。

我还尝试了用于断开连接图的在线 DFS 可视化工具，他们还支持它仅涵盖 1 个组件。但我还是想确认

• https://www.cs.usfca.edu/~galles/visualization/DFS.html
• https://visualgo.net/dfsbfs

Answer 1

在断开连接的图的单个组件上开始搜索将仅搜索该组件；否则怎么可能呢？没有信息可用于决定何时、如何或在何处将搜索移动到不同的组件。

如果您想对断开连接的图执行完整搜索，您有两个高级选项：

• 对每个组件进行单独的搜索，然后添加一些逻辑以在多个结果中进行选择（如果需要）。这样做的优点是易于并行运行搜索的分区逻辑。
• 添加逻辑以指示如何将组件组合成“单个”图表。对此有两个想法：
  • 添加一个虚拟根节点，并将组件作为其子节点。对于仅涵盖一个组件但您希望同时使用所有三个组件的工具来说，这将是一种巧妙的解决方法。这还意味着，如果您正在搜索单个最佳结果，则无需任何额外检查即可保证获得全局最佳结果。
  • 将组件放入列表中，并添加在当前搜索完成时跳转到下一个组件的逻辑。如有必要，添加额外的逻辑来比较多个潜在的搜索结果。

请注意，相同的推理也适用于广度优先搜索。