は、次の規則に従うことにより、我々は、このグラフ上でDFSを実行すると仮定しますid。DFS発見と仕上げ回
•私たちは、再起動する最小 ID
と白の頂点からそれを実行する必要があるときは、その結果DFSフォレストを表示します。さらに、すべての頂点について、その発見時間および終了時間を示す。
6
|
1--2--7--3--4--5--8
質問は結果の森を表示するために私に尋ねる、まだ私は一本の木を生産しています：次のようにも。＃/ =発見し、＃/＃は、=
DFSツリーを終えました、私は間違って何をしたのですか？
あなたは何も見逃しました。フォレストはグラフのセットであり、したがって0つのグラフを含むことさえ許されます。あなたの結果のグラフは絶対に有効です。一部の講師は独自の定義を使用する傾向があるため、スクリプトでその内容を再確認することをおすすめします。 DFSトラバーサルに関しては、1からの任意のノードのパスが存在することを示すことは完全に有効であり、非常に簡単です。
iveは実際にノード2に行くのは間違っていました。しかし、あなたの右は – 101ldaniels
@ 101ldanielsでした。このルールは次のとおりです。*すべての頂点で、IDの昇順で外側のノードを処理してください。* 3の前に2を横切るように要求してください。 – Paul
その場合には処理されたノード8が6になります。 – 101ldaniels
フォレストは1+ツリーのグループを指します。私が何かを見逃していない限り、単一の木の森も有効です。 – ilim