无向图邻接表两种场景的时间复杂度是否均为O(V+2E)？

核心结论 #

两种场景的时间复杂度最终都可简化为 O(V+E)，而非严格的O(V+2E)。

为什么O(V+2E)等价于O(V+E)？ #

大O表示法只关注算法时间复杂度的量级趋势，常数系数会被忽略。2E和E属于同一量级，因此O(V+2E)可以直接简化为O(V+E)。

两种场景的具体分析 #

• 场景1：单个连通无向图
  以DFS或BFS遍历为例：每个顶点会被访问一次（耗时O(V)）；由于无向图的邻接表中每条边会被存储两次（比如顶点u的邻接表包含v，顶点v的邻接表也包含u），遍历过程中每条边会被处理两次，总边处理次数为2E，但这部分耗时仍属于O(E)量级。整体时间复杂度为O(V + E)。

• 场景2：多不连通子图的无向图
  遍历所有子图时，每个顶点依然只会被访问一次（O(V)），每条边同样会被处理两次（O(E)量级）。即使需要多次启动遍历（每个子图一次），总操作数的量级依然是顶点数加边数，最终时间复杂度还是O(V + E)。

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