图的邻接矩阵存储空间复杂度是多少？软件设计师解析

题目

用邻接矩阵存储一个有 n 个顶点的图时，无论边数多少，都需要一个 n×n 的矩阵来表示顶点之间是否相邻。其存储空间复杂度通常为（）。

A O(n²)

B O(n)

C O(log n)

D O(1)

题目类型：原创高频考点题用途：用于帮助理解软件设计师相关考点和答案解析，不等同于官方真题。

正确答案

答案解析

邻接矩阵使用 n×n 的二维数组表示图中任意两个顶点之间的连接关系，因此空间复杂度为 O(n²)。它适合边较多的稠密图，判断两点是否相邻也很方便。

选项分析

正确。n 个顶点对应 n×n 矩阵，空间复杂度为 O(n²)。

错误。O(n) 更接近只按顶点数量线性存储的情况，不符合邻接矩阵。

错误。O(log n) 常见于某些查找深度，不是矩阵存储空间。

错误。图规模变化时，矩阵空间不可能保持常数。

本题为什么容易错

这题容易被“边数很少”带偏。邻接矩阵即使图很稀疏，也要保留 n×n 的位置。

先看结论

简短答案

图的邻接矩阵需要多少存储空间，正确答案是 A（O(n²)）。邻接矩阵使用 n×n 的二维数组表示图中任意两个顶点之间的连接关系，因此空间复杂度为 O(n²)。它适合边较多的稠密图，判断两点是否相邻也很方便。

解析

易混淆概念对比表

概念	本题判断	区别要点	记忆提示
O(n²)	本题正确答案	正确。n 个顶点对应 n×n 矩阵，空间复杂度为 O(n²)。	看到题干核心场景时优先联想到它
O(n)	本题干扰项	错误。O(n) 更接近只按顶点数量线性存储的情况，不符合邻接矩阵。	看到该词不要急着选，先判断是否真正解决题干问题
O(log n)	本题干扰项	错误。O(log n) 常见于某些查找深度，不是矩阵存储空间。	看到该词不要急着选，先判断是否真正解决题干问题
O(1)	本题干扰项	错误。图规模变化时，矩阵空间不可能保持常数。	看到该词不要急着选，先判断是否真正解决题干问题

本题易混淆选项怎么区分

O(n)：错误。O(n) 更接近只按顶点数量线性存储的情况，不符合邻接矩阵。
O(log n)：错误。O(log n) 常见于某些查找深度，不是矩阵存储空间。
O(1)：错误。图规模变化时，矩阵空间不可能保持常数。

复习

知识点详解

空间复杂度是软件设计师考试中需要结合场景理解的考点。围绕“图的邻接矩阵需要多少存储空间”这类题目，复习时要先看题干描述的是概念定义、适用场景、作用效果，还是与其他选项的区别。本题的题干关键词是“用邻接矩阵存储一个有 n 个顶点的图时，无论边数多少，都需要一个 n×n 的矩阵来表示顶点之间是否相邻。其存储空间复杂度通常为（）”，它指向的核心答案是 A（O(n²)）。

备考速记

备考速记：题干如果强调“空间复杂度”中的关键目标，就先联想到空间复杂度；如果选项里出现 O(n)、O(log n)、O(1)，不要只看名称熟悉，要判断它们是否真正对应题干场景。

空间复杂度在空间复杂度场景中的作用

空间复杂度在本题中的核心价值，是解决“用邻接矩阵存储一个有 n 个顶点的图时，无论边数多少，都需要一个 n×n 的矩阵来表示顶点之间是否相邻。其存储空间复杂度通常为（）”这个场景问题。复习时不要只背选项名称，还要理解它为什么适用于该场景，以及它能解决哪类安全、流程或管理问题。

拓展

解题思路

题干已经说需要 n×n 的矩阵，矩阵元素个数就是 n²。不要因为边数少就改答案，邻接矩阵的空间主要由顶点数决定。

考点定位

图的存储结构常考邻接矩阵和邻接表。邻接矩阵空间 O(n²)，邻接表更适合稀疏图。

易错提醒

邻接矩阵适合稠密图，邻接表适合稀疏图。
邻接矩阵判断两个顶点是否相邻通常很快。
无向图的邻接矩阵通常关于主对角线对称。

备考提示

复习图存储时，把邻接矩阵和邻接表从空间、查边、遍历邻接点三个角度对比。
看到 n×n 矩阵，空间复杂度基本就是 O(n²)。

你可能还想了解

图的邻接矩阵需要多少存储空间？
空间复杂度是什么？
空间复杂度在软件设计师考试中怎么考？
软件设计师空间复杂度题怎么理解？
邻接矩阵空间复杂度怎么考？
软件设计师图存储结构怎么考？

本文小结

本题核心考点是空间复杂度在空间复杂度场景中的判断和应用。遇到类似题目时，先看题干描述的目标，再判断哪个选项最符合场景；本题应选择 A（O(n²)）。

图的邻接矩阵需要多少存储空间？