设有向图 G=(V,E)，顶点集 V={v0,v1,v2,v3}，边集 E={<v0,v1

，< v0,v2 ，< v0,v3 ，< v1,v3 }。若从顶点 v0开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是（）。

图的遍历

A. 2 B. 3 C. 4 D. 5

正确答案：D

画出该有向图图形如下：

结论

答案为 D，共有 5 种不同的 DFS 首次访问序列。

推导

从 v0 开始，DFS 每次在当前顶点的未访问邻接点中选择一个并继续深入；走不通时回溯，再尝试下一分支。逐一枚举得到：

1. <v0,v1,v3,v2>
2. <v0,v2,v3,v1>
3. <v0,v2,v1,v3>
4. <v0,v3,v2,v1>
5. <v0,v3,v1,v2>

因此计数为 5，选 D。拓扑序列题的计数方法是逐步选择剩余入度为 0 的顶点；本题虽考 DFS，仍应保持“每一步只从当前合法候选中选取”的计数纪律。

易错点

第三个序列中的顶点是 v1；DFS 序列记录首次访问顺序，回溯本身不重复记录顶点。