连通图中BFS时间复杂度为O(E)的推导是否正确？

这个推导是正确的，具体分析如下：

1. 连通图的边数性质：连通图的边数m满足m≥n-1（n为顶点数），这是因为连通图的最少边数对应生成树，此时m=n-1；非树结构的连通图边数更多。由此可以推导出n ≤ m+1，这个不等式完全成立。

2. 大O符号的等价转换：
   根据上述不等式，m+n ≤ m + (m+1) = 2m + 1。
   按照大O复杂度的定义，常数项和系数不影响最终的复杂度类别，因此O(2m+1)等价于O(m)。
   这就说明O(m+n)是O(m)的子集，即连通图的BFS时间复杂度可以简化表示为O(m)。

额外补充：当连通图是树（m=n-1）时，m+n=2n-1，此时O(m+n)=O(n)，而O(m)=O(n)，两者等价；当图是稠密连通图（m远大于n）时，O(m+n)显然等价于O(m)，两种场景都符合推导结论。

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