图BFS时间复杂度疑问：为何是O(V+E)而非O(V*平均度)

核心结论：这两种表述本质等价，只是从不同角度描述同一计算量 #

我们一步步拆解：

1. 图的度数与边数的关系

   • 对于无向图：每条边连接两个顶点，因此每条边会被计入两个顶点的度数中，所有顶点的总度数 = 2E。
   • 对于有向图：每条边是从一个顶点指向另一个，仅计入起点的度数，总度数 = E。

2. BFS的时间消耗拆解
   BFS的时间由两部分组成：

   • 顶点处理：每个顶点只会入队一次、出队一次，外层循环总共执行V次，这部分时间是O(V)。
   • 邻接节点遍历：每个顶点出队后，会遍历其所有邻接节点（对应你代码里的for(const v of adj[el])循环）。所有顶点的邻接节点遍历总次数，等于图的总度数——无向图是2E，有向图是E。这部分时间是O(E)（大O表示法忽略常数系数，2E和E都属于O(E)）。

   把两部分加起来，总时间复杂度就是O(V + E)。

3. 为什么和O(V*平均度数)等价
   图的平均度数 = 总度数 / V。代入总度数的关系：

   • 无向图：平均度数 = 2E/V → V*平均度数 = 2E = O(E)
   • 有向图：平均度数 = E/V → V*平均度数 = E = O(E)

   所以O(V + V*平均度数) = O(V + E)，两者是完全等价的表述，只是前者从顶点的平均邻接数角度描述，后者从顶点和边的总量角度描述。

4. 结合你的代码验证
   你的代码中：

   • 外层while循环执行V次（每个顶点恰好出队一次），对应O(V)的时间。
   • 内层for循环的总执行次数是所有顶点的度数之和（无向图为2E），对应O(E)的时间。
     两者相加就是O(V+E)，而你提到的O(V*平均度数)只是换了一种计算总遍历次数的方式，本质和O(E)是一回事。

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