algorithm - G的节点与DFT的深度优先遍历关系

Question

令 G 为无向图。考虑 G 的深度优先遍历，并令 T 为生成的深度优先搜索树。令 u 为 G 中的一个顶点，令 v 为遍历中访问 u 后访问的第一个新(未访问)顶点。以下哪项陈述总是正确的？

(A) {u,v} 必须是 G 中的边，并且 u 是 T 中 v 的后代

(B) {u,v} 必须是 G 中的边，并且 v 是 T 中 u 的后代

(C) 如果 {u,v} 不是 G 中的边，则 u 是 T 中的叶子

(D) 如果 {u,v} 不是 G 中的边，则 u 和 v 必须在 T 中具有相同的父级。

============================================= ==========================

Correct answer is (C)

但我卡在了 (B)，我没有得到 (B) 的任何反例

Answer 1

考虑下图(实际上是一棵树)。

G := (V, E) where
V := {a, u, v} and E := {{a,u}, {a,v}}.

G 中的深度优先遍历可以首先访问a，然后是u，最后是v。在 u 被访问的点，v 是下一个未访问的节点。但是，{u, v} 不是 E 中的边，因此语句 (B) 为假。