对于断开连接的图,DFS(G,v) 的行为如何?
假设一个图有 3 个连通分量,并且 DFS 应用于这 3 个连通分量之一,那么我们是访问每个分量还是只访问应用了 DFS 的顶点。
意思是这样说对吗
DFS on a graph having many components covers only 1 component.
我还尝试了用于断开连接的图形的在线 DFS 可视化工具,它们也支持它仅涵盖 1 个组件。但还是想确认一下
最佳答案
在断开连接的图形的单个组件上开始搜索将仅搜索该组件;否则怎么可能呢?没有信息可以决定何时、如何或在何处将搜索移动到不同的组件。
如果您想对断开连接的图执行完整搜索,您有两个高级选项:
- 启动对每个组件的单独搜索,然后添加一些逻辑以在多个结果中做出选择(如有必要)。这具有用于并行运行搜索的简单分区逻辑的优点。
- 添加逻辑以指示如何将组件组合成“单个”图表。两个想法:
- 添加一个虚拟根节点,并将组件作为其子节点。对于只涵盖一个组件但您想同时使用所有三个组件的工具,这将是一个巧妙的解决方法。这也意味着,如果您要搜索单个最佳结果,则可以保证您获得全局最佳结果,而无需任何额外检查。
- 将您的组件放在一个列表中,并添加在当前搜索完成时跳转到下一个组件的逻辑。如有必要,添加额外的逻辑来比较多个潜在的搜索结果。
请注意,同样的推理也适用于广度优先搜索。
关于algorithm - 断开连接的图形上的 DFS,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41844408/