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

本文详解在使用邻接矩阵存储无向图并执行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 visit
ed[] = new boolean[n]; // ← 占用 O(V) 空间
Queue 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 邻接表）往往是空间复杂度的决定性因素。在面试或系统设计中，应主动澄清上下文，避免因定义偏差导致结论错误。