关于BFS时间复杂度O(|V|+|E|)的疑问及图表示关联咨询

一、为什么是O(|V|+|E|)？ #

BFS的核心逻辑是通过队列逐层遍历顶点：从起始点出发，先访问所有直接邻接的顶点，再依次处理这些顶点的邻接点，直到所有可达顶点都被访问。

• 顶点层面：每个顶点只会被入队、出队、标记已访问各一次，这些都是常数时间操作，总开销为O(|V|)。
• 边层面：每条边都会被处理一次——无向图中每条边会出现在两个顶点的邻接列表里，但BFS中只会在第一次遍历到这条边时完成有效处理；有向图中每条边只属于一个顶点的邻接列表，仅被处理一次。所有边的总处理开销为O(|E|)。
• 把顶点和边的开销相加，总时间复杂度就是O(|V|+|E|)。

二、图的表示方式对复杂度的影响 #

这个表达式的成立，和邻接表这种图的主流高效表示方式直接相关，对比另一种常见表示邻接矩阵就能看明白：

1. 邻接表（Adjacency List） #

邻接表是每个顶点存储一个邻接顶点的列表，遍历某个顶点的所有邻接边时，只需遍历对应列表，时间和该顶点的度数成正比。所有顶点的度数之和在无向图中是2|E|、有向图中是|E|，因此遍历所有边的总时间为O(|E|)，加上顶点的O(|V|)，总复杂度正好是O(|V|+|E|)，这也是资料里默认用这个表达式的原因。

2. 邻接矩阵（Adjacency Matrix） #

如果用邻接矩阵实现BFS，复杂度会变成O(|V|²)。因为邻接矩阵是|V|×|V|的二维数组，检查某个顶点的邻接点时，必须遍历整个数组的一行（共|V|个元素），不管实际有多少条边。每个顶点都要遍历一行，总时间就是|V|×|V|=O(|V|²)，这时边的数量不再主导复杂度。

三、补充说明 #

• O(|V|+|E|)是连通图最坏情况下的时间复杂度，如果是不连通图，BFS需要遍历每个连通分量，总复杂度依然是O(|V|+|E|)，因为所有顶点和边都会被处理一次。
• 这个复杂度属于线性时间复杂度，它和图的总规模（顶点数加边数）成正比，是图遍历算法里的高效类别。

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