木のようにDFSツリー

Question

質問が行くであるかどうかを確認します。我々は、我々はの隣人を探索する開始頂点と 順に応じて、グラフのために多くの可能性のあるDFSツリーが存在する可能性があることを知っている

各頂点。
与えられた与えられたグラフG =（V、E）では、この木の各辺がEにある となるようにルート木Tが与えられます。TがGのDFSツリーであるかどうかを決定する効率的なアルゴリズムを設計します。

「ツリーTはDFSツリーではありません」という意味は何ですか（グラフ全体にまたがっているとします）。

私が隣接リスト表現（私が本質的な主張をしているものと推測しています）にツリー頂点の順序がない場合、私はどんな方法でもトラバースし、質問に与えられたツリーを作成できます。

EDIT：「DFS以外のツリーT」について知りたかったと思います。すべての子が必要であるという制約があるため、すべてのDFSで作成されるツリーです親に戻る前にDFSツリーで最初に訪問しました。それでも、誰でも効率的なAlgoを手助けすることができます。

例えば：

A - B
           /           
\ C - D

このグラフは、ツリーTを有するもの：
A - B
           /           
\ C   D

が、これは有効なDFSツリーをイマイチ！
DFSは頂点Aから始まります。

ありがとうございます！

Answer 1

DFSが結果のラベリングを一意に決定しないという事実は、ノードの子が訪問される順序がないという事実による。私の理解のために、与えられたグラフGのツリーTがDFSツリーであるかどうかをチェックすることは、以下のように行うことができる。

Tに最小ラベルを持つノードを見つけます。これは現在のノードvであり、この時点でDFS検索が開始されるルートです。訪問先としてvをマークしてください。

vの未訪問の子プロセスをGに再帰的に処理します。これらがTと同じでない場合、TはGというDFSツリーではありません。同じ場合は、TのDFS番号の昇順に処理し、通常どおりDFS番号を割り当て、訪問先ノードをマークします。割り当てられたDFS番号がTのDFS番号と一致しない場合は、ツリーTはDFSツリーGになることはできません。一方、すべてのDFS番号をTのものと一致するように割り当てることができる場合、TがGのDFSツリーであることを建設的に証明しています。