问题是：
我们知道一个图可能有许多dfs树，这取决于起始顶点和
探索每个顶点邻域的顺序。
给定一个连通图G=（V，E），给出一个有根树T，使得该树的每条边
设计了一种有效的判定t是否为g的dfs树的算法。
“tree T不是DFS树”的含义是什么（假设它跨越整个图形）？
如果在邻接列表表示中没有树顶点的任何顺序（我假设问题本身就是这样），我可以以任何方式遍历并创建问题中给定的树。
编辑：我想我知道了一个“非DFS树T”，它只是一个跨树，但不可能在任何可能的DFS中创建，因为我们有一个限制，在返回父级之前，必须首先访问DFS树中的所有子级不过，有谁能帮上忙呢？
如：
A--B
/\
___C-D
此图的树T为：
A--B
/\
___C D
但这不是有效的dfs树！
dfs从顶点a开始。
提前谢谢！
最佳答案
dfs不能唯一地确定生成的标签，这是因为没有访问节点的子节点的顺序。根据我的理解，检查给定图T的树G是否是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树。