すべての接続されていないグラフを見つけるために最適なBFSまたはDfsまたは非接合集合

Question

切断されたすべてのグラフを見つけるためにどのアプローチを使用すべきですか？

両方トラバーサル DFSと BFS としてトラバーサル方法であり、複数のトラバースによる。すべての接続されていないコンポーネントが見つかります。
もう1つの方法は、接続されていないコンポーネントを見つけるためにkruskal（MST）で使用されているように、のように、ディスジョイントセットにすることができます。

Answer 1

あなたはすべて切断グラフを見つける必要があると述べたという理由だけで、それがcompleteあるとして、私は深さ優先探索ではない、BFSを使用することをお勧めします。暗黙的に表された無限のグラフに適用すると、BFSは目的の状態を見つけるでしょう、あなたのシナリオでは、すべての切断されたグラフを見つけるでしょう。一方、DFSはゴール状態を含まないグラフの一部で失われ、本質的に失われる可能性があります。