有向グラフGと指定された頂点s∈Vが与えられている。 有向グラフの点集合がV。 また、sを根とする有

有向グラフGと指定された頂点s∈Vが与えられている。
有向グラフの点集合がV。

また、sを根とする有向木Tが与えられている。Tが最短路木であるかどうかを判定するアルゴリズムを深さ優先探索を用いて作れ。

という問題なのですが

やり方がわかりません。
教えてください！！

No.1 回答者： usa3usa 回答日時： 2018/10/15 22:11

＞やり方がわかりません。

だから、深さ優先探索がわからなければ、深さ優先探索を勉強する
最短路木がわからなければ、最短路木を勉強する
定義がわかれば、ほとんど答えもできたも同然では？

x∈V に対して、深さ優先探索アルゴリズムで頂点sからのパスを見つける
見つかったパスは最短のはずである　－＞　有効木Tにパスがあるはずである
パスが有効木Tに無かったら、Tは最短路木ではないよね