確定一個樹是一個DFS樹

Question

問題去爲：

我們知道，有可能是根據起始頂點和 中，我們探討的鄰居爲了圖許多可能的DFS樹每個頂點。
給定一個連通圖G =（V，E），給出一個有根樹T，使得這棵樹的每個邊在E中存在 。設計一個有效的算法來確定T是否是G的DFS樹。

「樹T不是DFS樹」是什麼意思（假設它跨越整個圖）？

如果我在鄰接表中沒有任何樹頂點的排序（我認爲這個問題固有地聲稱），我可以以任何方式遍歷並創建問題中給出的樹。

編輯：我想我知道一個「非DFS樹T」，它只是樹的跨度，但不可能創造任何可能的DFS，因爲我們有一個限制，所有的孩子必須是在返回父級之前，先在DFS樹中訪問。不過，任何人都可以幫助高效的Algo。

例如：

A - 乙
           /  \
         Ç - d

該曲線圖中有一個樹T爲：
甲 - B
           /  \
         Ç  d

但心不是一個有效的DFS樹！
從頂點A開始的DFS。

在此先感謝！

Answer 1

DFS並未唯一確定結果標籤的事實是由於沒有訪問節點的子節點的順序。根據我的理解，檢查給定圖G的樹T是否爲DFS樹可以按如下方式完成。

在T中查找最小標籤的節點;這將是當前節點v，它在此處是開始DFS搜索的根。已訪問，標記v。

遞歸處理v的未訪問子女G。如果這些與T不相同，則T不是G的DFS樹。如果它們相同，則按T中的DFS號碼升序處理它們，照常分配DFS號碼並標記訪問節點。只要分配的DFS號碼與T中的DFS號碼不匹配，則樹號T就不能是G的DFS樹。另一方面，如果可以將所有DFS號碼分配爲與T中的號碼相匹配，則我們已經建設性地證明T是G的DFS樹。