哪種方法最適用於查找所有斷開圖形的Bfs或Dfs或Disjoint集合

Question

我們應該使用哪種方法查找所有斷開連接的圖形，以及爲什麼？

作爲BFS和DFS遍歷兩者都遍歷方法和由多個遍歷。我們可以找到所有斷開的組件。
而另一種方法可以是不相交集合用於kruskal（MST）中查找斷開的組件。

Answer 1

很簡單，因爲你說，你需要找到所有斷開的圖表，我會建議使用BFS，因爲它是complete，深度優先搜索是沒有的。當應用於隱式表示的無限圖時，BFS將查找目標狀態，在您的方案中，將查找所有不連通的圖。另一方面，DFS可能在圖中不包含目標狀態的部分中丟失，實質上可能會丟失。