大门| 2007年大门|问题24

在有向无环图上执行深度优先搜索。设d[u]表示第一次访问顶点u的时间，f[u]表示对顶点u的dfs调用终止的时间。对于图中的所有边（u，v），下列哪项陈述总是正确的？ （A） d[u] （B） d[u] （C） f[u] （D） f[u]>f[v] 答复: （D） 说明： 在节点V启动DFS 1] 访问（V）->DFS（X）->访问（X）->DFS（U）->访问（U）->回溯（X）->回溯（V） 因此：d[U]>d[V]，d[U] 但是，访问顺序与完成顺序正好相反。 因此f[U]>f[V] 这个问题的小测验