無向グラフが接続されているかどうかを知る最も効率的なアルゴリズム

Question

グラフが接続されているかどうか検索するアルゴリズムを探しています。グラフは無向であり、私は解決策（複数ある可能性があります）または見つからない場合のみ検索します。私はアルグを探していた。おそらくO（logN）またはO（NlogN）に近い線形時間を実行します。

DFSはこのタスクに対応できますか、またはこの特定の問題の別の代替方法がありますか？

Answer 1

あなたが入力のいくつかの特定の順序を持​​っていない限りNは頂点の数である場合、入力自体のサイズO(N^2)にすることができ、あなたがNをどう定義するかに依存するようになるだろう、とあなたはそれ（のすべてを読み取るために必要とされますそれ以上に変化する可能性があります）。

DFSは、ノードの数+エッジの数で実行され、検出された新しい頂点の数を数えてグラフが接続されているかどうかを確認し、完了したら|V|であるかどうかを確認します。