graph - 無向グラフが接続されているかどうかを判断する

Question

しばらく前からこの投稿に出くわしました：

無向グラフがツリーかどうかを判断する最適なアルゴリズム

無向グラフが木であるかどうかを判断するには、サイクルがあるかどうかを確認するだけでよいと書かれています。しかし、グラフが接続されていることを確認する必要はありませんか? 木はつながっていて非環式であると教えられました。非周期性のみをチェックするだけで十分ですか?

ありがとう。

Answer 1

あなたが正しい。グラフが非循環の場合、それは森です。さらに、コンポーネントが 1 つしかない場合、それはツリーです。

言及されたアルゴリズムが行うことは、バック エッジを探すことです。見つかった場合、グラフはツリーではありません。エッジが見つからず、アルゴリズムがエッジを使い果たす前に n-1 個のエッジを訪問した場合、それはツリーです。 1 エッジ）。アルゴリズムがエッジを使い果たしたが、n-1 個の訪問済みエッジに到達しなかった場合、グラフが接続されていないため、ツリーではないことを意味します。