1

完了した宿題があり、100 点中約 3 点が次の質問に対するものです。

「有向グラフ上に DFS ツリーを構築するとします。その後、バック エッジがないことに気付きます。これはグラフについて何を示しているでしょうか?」

私はこれについていくつか考えましたが、これは、グラフをトポロジー的に横断する特定のパスが 1 つだけ存在するという暗黙の依存関係があることを意味するということだけを推論できます。残念ながら、ウェブ上のどこにもこれに関する情報を見つけることができなかったので、ここに回答を投稿して、誰かがその(不)正確性について検討できるかどうかを確認したいと思いました. この問題の解決に役立つ可能性のある追加の考えや指針があればお知らせください。

本当にありがとう!

4

2 に答える 2

0

任意の有向グラフで、DFS がバック エッジを報告しない場合、グラフにはサイクルがありません。

于 2014-10-01T00:56:41.180 に答える
0

もっと微妙な答えがあるかもしれませんが、私がすぐに思いついたのは、それはグラフにサイクルがないことを意味するということです。

于 2014-02-19T06:49:38.607 に答える