本文详解在使用邻接矩阵存储无向图并执行bfs路径判定时，如何准确计算整体空间复杂度——需同时考虑输入结构（o(v²)邻接矩阵）与算法辅助空间（o(v)队列和visited数组），最终空间复杂度为o(v²)。
在算法分析中，“空间复杂度”常被误认为仅指函数内部申请的额外空间（即辅助空间），但严格定义下，空间复杂度 = 输入数据所占空间 + 辅助空间。这一点对图算法尤为重要，因为图的存储方式会显著影响总空间开销。
以您提供的代码为例：图采用 V×V 邻接矩阵 adjMatrix 表示（其中 V 为顶点数）。该二维数组在堆内存中占据 O(V²) 空间——这是输入本身带来的不可忽略的开销。即使 BFS 函数 hasPath1 内部仅使用了：
- 一个 Queue
：最坏情况下入队所有顶点（如链状图从起点遍历到终点），空间为 O(V)； - 一个 boolean[] visited 数组：长度为 V，空间为 O(V)；
- 若干常量变量（n, vertex, i 等）：O(1)。
因此，辅助空间总计为 O(V)。但若题目问的是“整个程序的空间复杂度”（即 main 中构建图 + 调用 BFS 的全过程），则必须计入邻接矩阵的 O(V²) 存储开销：
int[][] adjMatrix = new int[n][n]; // ← 占用 O(n²) = O(V²) 空间 boolean visited[] = new boolean[n]; // ← 占用 O(V) 空间 Queue<Integer> queue = new LinkedList<>(); // ← 最坏 O(V) 空间
✅ 正确结论：
- BFS 算法本身的辅助空间复杂度为 O(V)；
- 整个解决方案（含输入图存储）的空间复杂度为 O(V²)。
⚠️ 注意事项：
- 若改用邻接表（如 List
[] graph 或 HashMap >），输入空间可降至 O(V + E)，此时整体空间复杂度通常为 O(V)（因 E ≤ V²，但稀疏图中 E ≪ V²）； - LinkedList 作为队列虽方便，但其节点对象存在额外内存开销；若追求极致空间效率，可考虑循环数组实现的队列（需预分配大小）；
- visited 数组不可省略——缺少它将导致重复入队、无限循环或错误结果，它是 BFS 正确性的必要空间代价。
总结：判断空间复杂度时，务必明确分析范围——是“纯算法逻辑”还是“端到端程序”。对于图问题，存储结构的选择（邻接矩阵 vs 邻接表）往往是空间复杂度的决定性因素。在面试或系统设计中，应主动澄清上下文，避免因定义偏差导致结论错误。
