depth-first-search - 哪种方法是最好的 Bfs 或 Dfs 或不相交集来查找所有断开连接的图

Question

我们应该使用哪种方法来查找所有断开连接的图，为什么？

由于BFS和DFS遍历都是遍历方法，并且是多次遍历。我们可以找到所有断开连接的组件。
另一种方法可以是kruskal (MST) 中使用的不相交集来查找不连接的组件。

Answer 1

仅仅因为你说你需要找到所有断开连接的图，我建议使用 BFS，因为它是完整的，深度优先搜索不是。当应用于隐式表示的无限图时，BFS 将找到目标状态，在您的场景中，将找到所有断开连接的图。另一方面，DFS 可能会在图中不包含目标状态的部分中丢失，并且本质上可能会丢失。