algorithm - 判断一棵树是否为 DFS 树

Question

问题如下:

We know that there may be many possible DFS trees for a graph depending upon the start vertex and the order in which we explore the neighbors of each vertex.
Given a connected graph G = (V, E), you are given a rooted tree T such that each edge of this tree is present in E. Design an efficient algorithm to determine if T is a DFS tree of G.

“树 T 不是 DFS 树”(假设它跨越整个图)是什么意思？

如果我在邻接列表表示中没有任何树顶点的排序(我假设这个问题本身就声称)，我可以以任何方式遍历并创建问题中给出的树。

编辑:我想我开始了解“非 DFS 树 T”，它只是跨越但不可能在任何可能的 DFS 中创建的树，因为我们有必须访问所有子级的限制在返回父级之前首先在 DFS 树中。尽管如此，任何人都可以帮助高效的算法。

例如:

甲--乙
/\
C-D

这个图有一个树 T 为:
A -- B
/\
C D

但这不是一个有效的 DFS 树!
DFS 从顶点 A 开始。

提前致谢!

Answer 1

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树.