算法|图遍历|问题12

考虑下面的图表，

在以下序列中：

(I) a b e g h f 
(II) a b f e h g
(III) a b f h g e 
(IV) a f g h b e  

上图中哪些是深度优先遍历？ （A） 一、 仅限II和IV （B） 只有我和IV （C） 二、 仅限III和IV （D） 一、 仅限III和IV 答复: （D） 说明： 我们可以检查所有DFS的以下属性。

In DFS, if a vertex '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是叶子），则控制返回到父对象，父对象然后访问下一个未访问的子对象。 这个问题的小测验