算法|图遍历|问题12

设G为无向图。考虑G的深度优先遍历，并将其作为所得的深度优先搜索树。假设u是G中的一个顶点，v是遍历中访问u后访问的第一个新（未访问）顶点。以下哪项陈述总是正确的？（门CS 2000） （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） 说明：

In DFS, if 'v' is visited
after 'u', then one of the following is true.
1) (u, v) is an edge.
     u
   /   
  v     w
 /     / 
x     y   z

2) 'u' is a leaf node.
     w
   /   
  x     v
 /     / 
u     y   z 

在里面 DFS ，在访问节点后，我们首先为所有未访问的孩子重现。如果没有未访问的子对象（u是叶子），则控制返回到父对象，父对象然后访问下一个未访问的子对象。 这个问题的小测验