邻接矩阵BFS算法空间复杂度解析

哈喽！今天心血来潮给大家带来了《图遍历算法空间复杂度分析：邻接矩阵+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 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 邻接表）往往是空间复杂度的决定性因素。在面试或系统设计中，应主动澄清上下文，避免因定义偏差导致结论错误。

理论要掌握，实操不能落！以上关于《邻接矩阵BFS算法空间复杂度解析》的详细介绍，大家都掌握了吧！如果想要继续提升自己的能力，那么就来关注golang学习网公众号吧！