题目

设有向图 G=(V,E)，顶点集 V={ v0 , v1 , v2 , v3 }，边集 E={< v0 , v1 >，< v0 , v2 >，< v0 , v3 >，< v1 , v3 >}。若从顶点 v0 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是（）。

错因

A

可能只想到了"v0 出发的第一步有 3 个邻居"中的 2 种走法，把第三种漏掉了；或者把"图遍历序列"误认为"先序"那种唯一序，只考虑了"先走 v1"和"先走 v2"两种粗粒度分支。漏掉了"先走 v3"这一支，并且没有展开各分支内部的细分。

B

只数了 v0 出发的 3 种"第一步"邻居（v1、v2、v3 各一种），但每条分支后面没有继续展开。事实上，第一步选 v1 时序列唯一（因为 v1→v3 是确定路径），但第一步选 v2 或 v3 时还各有 2 种后续走法——3 + 2 + 2 - 4 = 3 显然算不对，但容易停在"第一步 3 种"就不再细分。

C

数到了 v0 起手三种分支（v1、v2、v3）后，正确展开了其中一支为 2 种，但漏数了第二个有分支的支。比如展开了"v0→v2 后有 2 种"和"v0→v3 后有 2 种"中的一种，得到 1 + 2 + 1 = 4。少数了一条枝。

总解析

先列出每个顶点的出邻接表：

顶点	出邻居
v0	v1, v2, v3
v1	v3
v2	（无）
v3	（无）

DFS 从 v0 出发，"不同遍历序列"的差异来自：每次访问一个顶点后，邻居顺序未规定——可以选任意未访问的邻居先走。穷举所有选择即可。

枚举（按 v0 第一步走的方向分支）：

分支 ①：v0 → v1

• v1 的唯一未访问邻居 v3 → 走 v3
• v3 无出邻居 → 回溯到 v1 → 回溯到 v0
• v0 的剩余未访问邻居 = {v2} → 走 v2
• 序列：v0, v1, v3, v2（1 种）

分支 ②：v0 → v2

• v2 无出边 → 回溯到 v0
• v0 剩余 = {v1, v3}，2 种次序：
  • 先走 v1 → v3：v0, v2, v1, v3
  • 先走 v3 → 回溯 → v1（v1 剩余邻居只有 v3 已访问）：v0, v2, v3, v1
• （2 种）

分支 ③：v0 → v3

• v3 无出边 → 回溯到 v0
• v0 剩余 = {v1, v2}，2 种次序：
  • 先 v1 → v1 的邻居 v3 已访问 → 回溯 → 走 v2：v0, v3, v1, v2
  • 先 v2 → v2 无出 → 回溯 → 走 v1：v0, v3, v2, v1
• （2 种）

汇总：1 + 2 + 2 = 5 种。

#	序列
1	v0, v1, v3, v2
2	v0, v2, v1, v3
3	v0, v2, v3, v1
4	v0, v3, v1, v2
5	v0, v3, v2, v1

为什么 ① 只有 1 种：v1 之后只有 v3 可走，路径完全锁死；回到 v0 后只剩 v2，没有选择空间。

为什么 ② ③ 各 2 种：v0 的"剩余两个未访问邻居"都没有进一步分叉（v1 的邻居 v3 在 ② 里还没访问、③ 里已访问，但都不带来新分支），所以差异完全来自"v0 剩余两个邻居的选择顺序"，2! = 2 种。

方法论：枚举 DFS 序列的题，按"每次访问后的可选邻居数"做乘法/穷举，遇到"路径锁死"分支就 1 种、遇到"完全自由的 k 个邻居"分支就 k! 种。本题 1 + 2! + 2! = 5。

最终答案是 D（5）。