关于树与图遍历时间复杂度差异的疑问

不管是树的前/中/后序遍历，还是图的BFS/DFS遍历，底层的操作逻辑是统一的：

• 每个节点仅访问1次
• 每条关联边仅会被检查1次

所以两类遍历的原始时间复杂度都可以统一记作O(V + E)，两者的写法差异是由树、图本身的结构特性决定的。

为什么树遍历通常不写为O(V+E) #

树是特殊的无环连通图，满足固定的边数约束：E = V - 1。代入原始的复杂度公式可以得到：
O(V + E) = O(V + (V-1)) = O(2V - 1)
在渐进复杂度的计算规则下，常数项和低次项可以直接省略，最终等价于O(V)。由于树的边数永远和节点数成固定线性关系，没有独立变化的可能，因此直接简化为O(V)的写法更简洁直观。

为什么图遍历不能简化为O(V) #

图的边数E和节点数V没有固定的绑定关系，E是独立的变量：

• 稀疏图的边数可能和节点数接近，即E = O(V)
• 稠密无向完全图的边数可以达到E = V*(V-1)/2 = O(V²)
• 允许自环、多重边的图边数还可以更高

遍历图时，除了访问每个节点的开销，还需要遍历每个节点的所有邻接边，总开销直接由V和E的量级共同决定。如果直接简化为O(V)，完全无法体现边数对总耗时的影响，比如稠密完全图的遍历耗时是O(V²)，和O(V)的差距极大，因此必须保留E项，记作O(V+E)。

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