未使用visited数组的DAG上执行DFS的最坏时间复杂度是多少

核心结论 #

最坏情况下时间复杂度为指数级，即 O(2^V)，其中V为DAG的节点总数。

推导逻辑 #

• 首先明确规则：本题中DFS无访问标记，允许重复访问同一节点，且DAG本身不存在环，因此不会出现无限递归，所有遍历路径的长度最大为V。
• 最坏场景构造：将V个节点按拓扑序排列为v₁、v₂、…、v_V，构造完全DAG：对任意i < j，都存在一条从v_i指向v_j的有向边。该结构下从起点v₁出发的所有简单路径总数为2^(V-1)，每条路径都会被DFS完整遍历到。
• 复杂度计算：每条路径的遍历开销和路径长度正相关，最大为V，因此总操作数约为V·2^V，常规简化表示为O(2^V)。

补充说明 #

• 如果DAG为链式结构（每个节点仅有1条出边），就算没有visited数组，DFS的时间复杂度也为O(V+E)，和带visited数组的常规DFS复杂度一致，属于最优场景。
• 带visited数组的常规DFS，每个节点和每条边仅会被访问一次，稳定时间复杂度为O(V+E)，不受DAG结构影响。

内容的提问来源于stack exchange，提问作者j.i.l.l