无向图DFS遍历节点关系疑问：为何选项B不恒成立？

先明确问题背景：

设G为无向图，对G进行深度优先遍历（Depth First Traversal）得到DFS树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中必有相同父节点。已知正确答案为(C)，但我无法找到选项(B)的反例，对此存在困惑。

为什么选项B不成立？给你举个直观的反例 #

我们构建一个简单的无向图：

• 顶点集合：{1, 2, 3, 4}
• 边集合：{(1,2), (1,3), (3,4)}

现在从顶点1开始DFS遍历，假设邻接表顺序是优先遍历编号更小的邻接点：

1. 访问顶点1，标记为已访问。
2. 遍历1的邻接点，先访问2，2的父节点是1，加入DFS树T。
3. 访问顶点2的邻接点：只有1（已访问），于是回溯到1。
4. 回到1后，遍历它的下一个未访问邻接点3，访问3，3的父节点是1，加入T。
5. 访问顶点3的邻接点：1已访问，下一个是4，访问4，4的父节点是3，加入T。

现在看关键场景：u是顶点2——访问2之后，第一个被访问的未访问顶点是3（回溯过程不算访问新顶点，直到找到并访问3）。

• 首先，{u,v}即{2,3}，并不是图G中的边，直接违反了选项B中“{u,v}必是G中的边”的断言；
• 其次，在DFS树T中，3是1的后代，完全不是2的后代，也违反了选项B的后半句。

这个例子直接证明了选项B并非“始终成立”——存在这样的图和DFS遍历顺序，让选项B的两个结论都不成立。

再补充理解选项C为什么正确 #

如果{u,v}不是G的边，说明访问完u之后，我们不得不一路回溯，直到找到某个有未访问邻接点的节点x，才访问了v。而这个过程能发生的前提是：u的所有邻接点都已经被访问过了（否则我们在回溯之前就会优先访问u的其他未访问邻接点，轮不到v）。这意味着在DFS树T中，u没有任何子节点——也就是u是T的叶子节点，所以选项C的断言始终成立。

内容的提问来源于stack exchange，提问作者Geeklovenerds