图的DFS时间复杂度疑问：为何复杂度为O(e+v)？

你提到的疑问核心在于：DFS看似只访问顶点，但实际上遍历过程中每条边都会被处理一次或多次，这部分开销是时间复杂度包含边数e的关键。结合你给出的代码，具体拆解如下：

1. 顶点相关的时间开销 #

每个顶点只会被真正处理一次：当第一次访问顶点时，执行dfs.push_back(node)和freq[node] = true，后续再遇到该顶点（通过邻接边递归过来）会直接触发return。这部分操作的总时间是O(v)，v是顶点总数。

2. 边相关的时间开销 #

看help函数里的for(auto i : adj[node])循环：

• 对于无向图，每条边(u, v)会同时出现在u的邻接表和v的邻接表中，因此会被遍历两次；
• 对于有向图，每条边(u→v)只出现在u的邻接表中，会被遍历一次。

不管是哪种图，所有边的遍历总次数都是**O(e)**级别（e是边总数）。哪怕遍历到已访问的顶点会直接return，这个遍历边并触发递归的操作本身也是需要时间的，必须计入复杂度。

3. 结合代码的实例验证 #

比如一个有4个顶点的无向完全图，边数e=6。每个顶点的邻接表有3条边，总遍历次数是3×4=12，正好是2e，属于O(e)的范畴。加上4次顶点处理的O(v)，总时间开销就是O(4+6)=O(10)，对应O(v+e)。

综上，DFS的总时间开销是顶点处理的O(v)与边遍历的O(e)之和，因此时间复杂度为O(v+e)。

内容的提问来源于stack exchange，提问作者Hugf Nguyễn