邻接矩阵与邻接表存储下BFS和DFS的时间复杂度分析问询
2026-10-10
BFS与DFS时间复杂度分析
我们先直接给出不同存储结构下的复杂度结论，再做简单解释：
- 邻接矩阵存储
- BFS时间复杂度：
O(V²) - DFS时间复杂度：
O(V²)
- BFS时间复杂度：
- 邻接表存储
- BFS时间复杂度：
O(V+E) - DFS时间复杂度：
O(V+E)
- BFS时间复杂度：
复杂度逻辑解释
两种算法的核心执行逻辑一致：每个顶点仅会被访问一次，每条边仅会被检查一次，最终复杂度由存储结构的特性决定：
- 邻接矩阵是V×V的二维数组，查询某个顶点的所有邻接顶点时，需要遍历该顶点对应的整行数组（长度固定为V，V是顶点总数），不管实际有多少条有效边。总遍历次数固定为V*V，因此不管BFS还是DFS复杂度都是平方级。
- 邻接表仅存储每个顶点实际存在的邻接边，所有顶点的访问开销总和为O(V)，所有边的检查开销总和为O(E)（E是边总数），两者相加就是整体时间复杂度。
你之前认为的O(n)结论仅在稀疏图（边数和顶点数同阶，E≈V）且使用邻接表存储的场景下成立，此时O(V+E)可以简化为O(V)也就是你说的O(n)，但该结论不具备通用性。
内容的提问来源于stack exchange，提问作者Andro Star
相关产品推荐
相关产品推荐
