🏷️ 知识点：DFS

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

图的遍历 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 栈顶是否仍有未访问邻接点。

修改递归方式实现的图的深度优先搜索（DFS）算法，将输出（访问）顶点信息的语句移到退出递归前（即执行输出语句后立刻退出递归）。采用修改后的算法遍历有向无环图 G，若输出结果中包含 G 中的全部顶点，则输出的顶点序列是 G 的（ ）。

DFS 图的遍历

A. 拓扑有序序列 B. 逆拓扑有序序列 C. 广度优先搜索序列 D. 深度优先搜索序列

[tag_link]

正确答案：B

DFS 对任意有向边 vᵢ→vⱼ，DFS 从 vᵢ 沿该边访问 vⱼ 时，必须先完成 vⱼ 及其后继的递归，才能回到 vᵢ。把输出语句放在退出递归前，就会先输出后继 vⱼ，再输出前驱 vᵢ。因此所有边的终点都排在起点之前，输出序列是逆拓扑有序序列，选 B；若把该完成序列逆序，才得到拓扑序。