图中两点间所有路径的DFS变体算法时间复杂度分析

首先得明确一个核心点：寻找两点间所有可能路径的时间复杂度，本质由图中存在的路径总数决定，这和普通DFS找单条路径的复杂度完全不是一个量级——后者是线性的，前者往往是指数甚至阶乘级的，因为每个路径都需要被完整遍历并记录。

咱们一步步拆解：

1. 先明确前提：我们讨论的是「简单路径」 #

首先默认你要找的是不重复经过顶点的简单路径——如果允许重复顶点（走环），那强连通有向图里会有无穷多路径，时间复杂度直接是无穷大，这显然不是你要讨论的场景。

2. 最坏情况下的时间复杂度 #

不管是无向连通图还是强连通有向图，最坏情况都出现在图的连接性极强的时候（比如完全图/完全有向图）：

• 无向完全图：假设有n个顶点，从START到TARGET的简单路径数是(n-2)!（中间可以经过剩下n-2个顶点的任意排列）。每条路径的长度最多是n-1（经过所有顶点），总时间就是所有路径的长度之和，大概是O(n * (n-2)!) = O(n!)，也就是阶乘级。
• 完全强连通有向图：路径数会更多，比如从START出发，每一步都可以选剩下的任意顶点，路径数是指数级往上走，总时间复杂度也是指数/阶乘级，具体取决于图的结构，但肯定是远超线性的。

3. 你的DFS变体算法的复杂度分析 #

你提到“每访问一个顶点就将其颜色标记为BLACK”——这里我默认你的伪代码里有回溯逻辑：也就是在递归探索完当前顶点的所有邻接路径后，会把顶点的颜色改回白色（否则第一次走到TARGET后，其他路径会因为顶点被标黑而无法遍历，根本找不到所有路径）。

这种带回溯的DFS，本质是枚举所有可能的路径分支：每走到一个顶点，就标记它已访问（避免重复走同一个顶点形成环），探索完所有从该顶点出发的路径后，撤销标记（回溯），继续探索其他分支。

在这种情况下，算法的时间复杂度依然由路径总数决定：每条路径的遍历需要处理路径上的每个顶点和边，总时间就是所有简单路径的长度之和。最坏情况下就是上面说的阶乘/指数级，而最好情况（比如图是一条链，只有一条路径）就是O(V+E)，和普通DFS一样。

4. 和普通DFS的核心区别 #

普通DFS的目标是遍历图的结构（或者找任意一条路径），它每个顶点和边只会被访问一次，所以时间复杂度是O(V+E)——因为它不需要枚举所有可能的路径，找到一条就可以停止，或者遍历完整个图后结束。

而你的算法目标是枚举所有路径，这就必须遍历每一条可能的路径分支，而路径的数量本身是指数/阶乘级的，所以时间复杂度远远高于普通DFS。

内容的提问来源于stack exchange，提问作者choxsword