邻接矩阵Adjacency matrix

以顶点对为下标保存边是否存在或其权值。

核心约束: 矩阵项与对应边一致；无向图通常对称，无边标记须与合法权值区分。
适用问题: 稠密图、小规模全源路径计算及基于矩阵的图运算。
边界与取舍: 稀疏图使用稠密矩阵会浪费空间；多重边需额外表示，稀疏矩阵实现具有不同访问成本。

常见操作#

V 为固定顶点数；矩阵保存布尔连接关系或边权。

操作	时间复杂度	条件与说明
初始化稠密矩阵	$O(V^{2})$	清零或写入“无边”标记。
查边 / 插边 / 删边	$O(1)$	顶点编号已知，读写一个单元；无向图通常对称写两处。
枚举一个顶点的邻居	$O(V)$	扫描一行。
枚举所有边	$O(V^{2})$	没有独立边索引时需要扫描整个矩阵。
加入新顶点并重建连续矩阵	$O(V^{2})$	新矩阵需要迁移已有内容；预留容量可改变单次成本。

时间与空间#

时间复杂度: 查边 $O(1)$ ；邻居扫描 $O(V)$
存储空间: $O(V^{2})$

这里是稠密矩阵；稀疏矩阵的压缩表示有不同成本。

基础原理参考资料

Open Data Structures · AdjacencyMatrix矩阵表示和边操作成本。