下列选项中，不是下图深度优先搜索序列的是（）

图的遍历 DFS

A. V1, V5, V4, V3, V2 B. V1, V3, V2, V5, V4 C. V1, V5, V3, V4, V2 D. V1, V2, V3, V4, V5

正确答案：D

结论

D 不是该图的 DFS 首次访问序列；A、B、C 可以通过改变邻接点选择顺序和回溯时机得到。

推导

DFS 使用栈式深入：访问一个顶点后，必须先从它的未访问邻接点继续深入；只有当前顶点没有可走的未访问邻接点时，才回溯到栈中上层顶点。图中从 V1 访问 V2 后，V2 的未访问邻接点中应先沿图示边访问 V5；图中没有从 V2 指向 V3 的边。因此 D 不可能：它的第二步 V2→V3 不合法，且此时 V2 仍有未访问的 V5 分支。其余选项均可按图片中的真实邻接关系逐步深入并在必要处回溯得到。

易错点

不能只检查序列中顶点是否都出现，也不能凭想象补边；每一步都要对照图片中的真实边，并判断当前 DFS 栈顶是否仍有未访问邻接点。