请告诉我我的证明是否正确
我们有一个连接的图，以及 V(G) 中的特定顶点 u。
假设我们计算根于您的 G 的 dfs 树并获得树 T.现在假设我们计算根植于您的 G 的 bfs 树，我们得到相同的树 T.
证明这是可能的唯一方法是如果 G=T
矛盾证明。
假设 dfs 树和 bfs 树等于 T，但 G 不等于 T.
这意味着 G 至少包含一个不在 T 中的边.
我们也知道任何这样的边都是循环的一部分，否则它们就会在 T 中.
所以至少有一个循环C= p1, p2, p3, p_{k}与p_{k} = p1， 由不同的节点组成k>= 3，在G.假设
dfs和bfs算法会在节点p1遇到循环。
Dfs 将在其树(p1, p2)、....、(p_{k-2}、(p_{k-1})中添加以下边，而 bfs 首先将边(p1,p2)、(p1,p_{k})添加到其树中。
我们已经看到 dfs 树不等于 bfs 树，因为 bfs 包含(p1,p_{k})而 dfs 不包含此边。
这与我们的假设相矛盾，即 dfs 和 bfs 具有相等的树，并表明 G=T 一定是这种情况。
该定理仅适用于无向图(以任何强连接的圆二合图作为反例)。
回到无向图，为了直观地方法，请注意 dfs 最大化树高，而 bfs 最小化树高。这意味着在击中的第一个圆C，覆盖C的子树会有所不同。
你的证明正式确定了这个想法，所以总的来说我会说没关系。
您没有指定 dfs 选择策略，因此存在 2 个小错误：
-
代替
(p1,p2)，则 dfs 可以包含(p1,p_{k})条边或根本不包含任何边 ( )。当然，dfs 永远不会包含两个边，而 bfs 总是会。 -
Dfs 不一定
k-1圆边添加到T。然而，在退回p1之前，它将访问所有圆顶点，因此此时所有圆顶点都将添加到T。因此，不会添加(p1,p_{k})(dfs 选择(p1,p2)首次击中p1)或(p1,p2)(其他)，或。
您可以通过证明一个小引理来形式化后者：
设(v, w)dfs 在步骤n中添加的边(wlog 假设 dfs 从v移动到w)，T(n)是步骤 (n) 的部分 dfs 树。然后，在添加来自E(G)的另一个边(w, x)之前，子图中[w]G'V(G) V(T(n))诱导的已连接组件的所有节点都将添加到 dfs 树中。