如何分析图遍历算法的空间复杂度（以邻接矩阵+BFS为例）

本文详解如何准确计算基于邻接矩阵存储的无向图中bfs路径判断算法的总空间复杂度，明确区分输入空间与辅助空间，并指出常见误区：仅关注队列而忽略图结构本身的存储开销。

在算法分析中，空间复杂度并非仅指算法运行时动态申请的额外内存（即辅助空间），而是包含两大部分：
✅ 输入空间：算法接收的输入数据所占用的内存；
✅ 辅助空间：算法执行过程中临时使用的额外内存（如队列、递归栈、布尔数组等）。

以您提供的 hasPath1 函数为例，我们逐项分析：

1. 输入空间：O(V²) —— 关键易忽略项

函数签名中，第一个参数是 int[][] adjMatrix，即一个 V × V 的二维整型数组（V = n = adjMatrix.length）。无论算法逻辑如何，该邻接矩阵本身已占据 Θ(V²) 空间。根据空间复杂度定义，输入数据所占空间必须计入总空间复杂度。这是

题解中标注 O(V²) 的根本原因。

2. 辅助空间：O(V) —— BFS 本身的开销

• boolean visited[] 数组：O(V)；
• Queue（LinkedList 实现）：最坏情况下需入队所有顶点（例如起点为叶节点、目标在另一分支末端），故队列长度上限为 V，即 O(V)；
• 其他变量（n, vertex, i 等）均为常量空间 O(1)。
  → 因此，纯 BFS 过程的辅助空间为 O(V)。

3. 总空间复杂度：O(V²) + O(V) = O(V²)

由于 V² 主导 V（当 V ≥ 2 时），根据大O记号的简化规则，最终空间复杂度为：

Space Complexity = Input Space + Auxiliary Space  
                 = O(V²) + O(V)  
                 = O(V²)

⚠️ 注意：若题目明确要求“仅分析 BFS 遍历过程的辅助空间”（如算法设计题中假设图已加载到内存），则答案应为 O(V)；但若问的是整个程序或函数的总空间复杂度（尤其输入由调用方提供），则必须包含邻接矩阵的 O(V²) 开销。

补充对比：邻接表场景

若改用邻接表（如 List[] graph）表示图，输入空间降为 O(V + E)（稀疏图下通常为 O(V)），此时总空间复杂度变为 O(V + E)，显著优于邻接矩阵。这也解释了为何实际工程中，大规模稀疏图普遍采用邻接表而非邻接矩阵。

综上，判断空间复杂度时务必明确分析范围——是“算法辅助空间”还是“程序总空间”。对于本题代码，O(V²) 是严谨且正确的答案。