与えられた無向グラフが木構造かどうか確かめるアルゴリズムの作成

Question

与えられた無向グラフが木構造かどうか確かめるアルゴリズムの作成しようとしています。

木構造になるためには
①全てのノードがつながっている
②ループを含むのはNG
以上のことを念頭において擬似コードを書きたいのですが、①の全てのノードがつながっているのチェックの仕方をどうやれば良いのでしょうか?

②の件に関しては深さ優先探索を取り入れて一度訪れたノードをvisited配列に格納しもし格納済みのノードに辿り着いてしまった場合はFalseを戻り値に、もしたどり着かなかった場合はTrueを返せばよいのかなとおもうのですが。

Answer 1

こんにちは。

②の検出完了後に、全てのノードを枚挙してvisited配列に含まれていないノードがあったらfalseでよいのでは？

ただ深さ優先探索は、全てのノードをルートにして探索するイメージでしょうか？
この場合は、各ルート毎に冒頭の処理をして、全てのノードを巡回するルートが１つもなければfalseで良いように思います。

取り敢えずの思いつきですから、もっと高速なアルゴリズムもある筈と思います。

Comments

[ijuya_yika]

お陰様で納得が行きました。迅速なご回答ありがとうございます。

Answer 2

Python2.7用ですがコードもあります。
Check if a given graph is tree or not

ツリーとは連結(connected)かつ閉路(cycle)がないグラフといえます。
上記では、閉路を探しつつvisitedフラグを埋めておき、閉路がなければすべてvisitedか（連結か）で判定しているようです。

Comments

[ijuya_yika]

迅速なご回答ありがとうございます。