邻接矩阵怎么存无向图？5 分钟读懂 GraphAdjMat 的增删边与本地运行

邻接矩阵怎么存无向图？5 分钟读懂 GraphAdjMat 的增删边与本地运行

【免费下载链接】f3dFast and minimalist 3D viewer.项目地址: https://gitcode.com/GitHub_Trending/f3/f3d

hello-algo 仓库里的GraphAdjMat用一张邻接矩阵（adjacency matrix）存下整张无向图。下面带你把顶点索引约定、边与顶点的增删、本地运行方式一次讲清，跑通之后你也能自己做「矩阵还是列表」的选型判断。

先搞懂：一张 n×n 矩阵如何对应无向图的顶点索引

先放下代码，看看邻接矩阵到底在画什么。设图里有 $n$ 个顶点，我们摆一张 $n \times n$ 的方阵 $M$，让第 $i$ 行、第 $i$ 列各自代表第 $i$ 个顶点；格子 $M[i][j]$ 填 1，说明顶点 $i$ 与顶点 $j$ 之间存在边，填 0 说明没有。于是「两顶点连不连」这件事被翻译成「某一行某列那个格子是几」——查它只要按下标一读。

顺着这张方阵往下看，有三件很自然的事。主对角线上那一串 $M[i][i]$ 基本是空白的：简单图里顶点不会连自己，所以对角恒为 0，留着也没意义。再看无向边，$(i,j)$ 与 $(j,i)$ 说的是同一条边，整张矩阵因此关于主对角线左右对称，改一格就得连带改它的镜像。最后，0/1 只是最省事的取值，把 1 换成任意权值，这张表就能顺带表示带权图。

代价同样清楚：加边、删边、查边都是按下标直接改一格，稳在 $O(1)$；可方阵本身就占 $O(n^2)$ 空间，边再稀疏也得把整张表撑满。这正是它偏爱稠密图、而稀疏图另找邻接列表登场的原因。

无向图邻接矩阵示意图：顶点列表与 n×n 邻接矩阵的对应关系

关键约定：为什么边要传顶点索引而不是顶点值

📌 这里藏着最容易踩的坑，值得单独拎出来。GraphAdjMat里所有边用的都是「顶点索引」，不是「顶点值」。比如vertices = [1, 3, 2, 5, 4]，那么边[0, 3]连的是下标 0 的顶点（值 1）和下标 3 的顶点（值 5），也就是 1 与 5 相连——绝不是值 0 与值 3 相连。把「值」和「索引」混用的那一刻，矩阵就会悄悄画错。构造函数的注释也正是冲这一点提醒我们：edges 里的元素对应 vertices 的下标。

逐段拆解 GraphAdjMat：从增删边到扩行缩列

我们按「边 → 顶点 → 构造」的顺序拆。为什么先讲边？因为它是这份实现里最核心、也最能体现对称性的部分。

增删边 add_edge / remove_edge：为什么一次写两个格子

def add_edge(self, i: int, j: int): # 参数 i、j 对应 vertices 中的顶点索引 # 拦截越界与 i == j（自环） if i < 0 or j < 0 or i >= self.size() or j >= self.size() or i == j: raise IndexError() # 无向图矩阵关于主对角线对称，(i, j) 与 (j, i) 等价 self.adj_mat[i][j] = 1 self.adj_mat[j][i] = 1 def remove_edge(self, i: int, j: int): if i < 0 or j < 0 or i >= self.size() or j >= self.size() or i == j: raise IndexError() self.adj_mat[i][j] = 0 self.adj_mat[j][i] = 0

先回答「为什么一次写两个格子」。无向边天生双向，如果你只写adj_mat[i][j]，那从 $j$ 看 $i$ 就会得到「无边」的错误结论，对称性当场被打破。两格同写、同清，是对称性始终成立的唯一保证，而且只是两次下标赋值，$O(1)$。

再看那段 if 拦得有点「凶」。它把负索引、越界索引、i == j（自环）三种非法输入统统挡在门外，统一抛IndexError。为什么要拦自环？回到前面那句「主对角线无意义」——与其允许对角线出现一个无意义的 1，不如在入口直接拒绝，让简单图的主对角线永远干净。remove_edge与add_edge结构完全对称：同样的五项校验，然后把两个对称元素归 0。至于「两顶点是否相邻」的查询，直接读adj_mat[i][j]即可，这就是文档里说的「边操作全部 $O(1)$」的具体所指。

增删顶点 add_vertex / remove_vertex：如何扩行扩列、缩行缩列

def add_vertex(self, val: int): n = self.size() self.vertices.append(val) new_row = [0] * n self.adj_mat.append(new_row) for row in self.adj_mat: row.append(0) def remove_vertex(self, index: int): if index >= self.size(): raise IndexError() self.vertices.pop(index) self.adj_mat.pop(index) for row in self.adj_mat: row.pop(index)

新增顶点，矩阵就得从 $n \times n$ 长成 $(n+1) \times (n+1)$。新顶点暂时和谁都「无边」，所以新行、新列必须全 0。代码分三步落地：追加顶点值 → 追加一行全 0 向量 → 给既有每一行末尾各补一个 0，等价于新增一列。三步合计扫一遍既有行，$O(n)$。

删除是扩容的逆操作：先校验index不越界，再从vertices弹出顶点值、删掉矩阵第index行，然后对每一行pop(index)削掉第index列。有一个隐含前提要小心——删掉某顶点后，它后面的顶点索引会整体前移一位，你手里旧的索引在删除之后必须重新换算。

构造函数init：复用上面四步完成建图

def __init__(self, vertices: list[int], edges: list[list[int]]): self.vertices: list[int] = [] self.adj_mat: list[list[int]] = [] for val in vertices: self.add_vertex(val) for e in edges: self.add_edge(e[0], e[1])

构造函数没有另起炉灶，而是把两个空列表准备好，然后循环调用add_vertex铺顶点、add_edge铺边。这样「演示文件里的简化版」和「完整版源码」共享同一套操作语义，行为天然一致。注意它先加完所有顶点、再加所有边，顺序不能反——否则add_edge里那套size()校验会立刻报错。完整版源码见ru/codes/python/chapter_graph/graph_adjacency_matrix.py，每个方法都带文档字符串，语义与上文逐一对应。

如何本地运行 GraphAdjMat 并跟踪状态变化

仓库自带一段驱动代码，跑完「建图 → 加边 → 删边 → 加顶点 → 删顶点」的完整流程：

vertices = [1, 3, 2, 5, 4] edges = [[0, 1], [0, 3], [1, 2], [2, 3], [2, 4], [3, 4]] graph = GraphAdjMat(vertices, edges) graph.add_edge(0, 2) graph.remove_edge(0, 1) graph.add_vertex(6) graph.remove_vertex(1)

与其逐句念，不如用一张状态演进表看全貌（v[i]即vertices[i]）：

阶段	操作	vertices 序列	矩阵规模
初始	构造函数	[1, 3, 2, 5, 4]	5×5
1	add_edge(0, 2)	[1, 3, 2, 5, 4]	5×5
2	remove_edge(0, 1)	[1, 3, 2, 5, 4]	5×5
3	add_vertex(6)	[1, 3, 2, 5, 4, 6]	6×6
4	remove_vertex(1)	[1, 2, 5, 4, 6]	5×5

值得留意第 4 步：remove_vertex(1)删掉的是vertices[1]，即值为 3 的顶点，缩回 $5 \times 5$ 后其余顶点索引整体前移。完整版还会在每步之后调用print()配合print_matrix把当前矩阵打印出来，方便你核对上面这张表。

想逐指令观察内存变化，可以用 Python Tutor 演示文件ru/codes/pythontutor/chapter_graph/graph_adjacency_matrix.md。这个文件形态特殊：正文只有一行pythontutor.com/render.html链接，完整可运行代码被 URL 编码后作为 fragment 参数嵌进链接里，把 fragment 解码就得到完整程序，头部还留了[file]{...}-[class]{graph_adj_mat}这类注释，声明它与源码文件的映射关系。本地直接跑源码则更省事：

python3 ru/codes/python/chapter_graph/graph_adjacency_matrix.py

脚本会按「初始化 / 加边 / 删边 / 加顶点 / 删顶点」五个阶段分别打印顶点列表与邻接矩阵。

选型对照：邻接矩阵还是邻接列表

仓库同目录下的对照实现ru/codes/python/chapter_graph/graph_adjacency_list.py用dict[Vertex, list[Vertex]]存「顶点 → 邻点列表」，把两者的差异摆在一起就清楚了：

维度	邻接矩阵GraphAdjMat	邻接列表GraphAdjList
存储结构	list[list[int]]二维数组	dict[Vertex, list[Vertex]]
空间	$O(n^2)$，与边数无关	$O(n + e)$
边操作	$O(1)$，改两个对称元素	追加/删除列表元素，需线性查找定位
删顶点	$O(n)$，缩行缩列	$O(n^2)$，删自身项后遍历其余列表remove
边查询	$O(1)$，直接读M[i][j]	$O(\deg(v))$，遍历对应列表
异常类型	IndexError（越界/自环）	ValueError（顶点不存在/自环）

给一句选择建议：顶点稠密、又要反复「查边」的场景（比如最短路径算法不停试探邻接关系），用邻接矩阵；边数远小于 $n^2$ 的稀疏图、且操作以遍历为主，用邻接列表更省内存。文档ru/docs/chapter_graph/graph.md还提到一个进阶方向——邻接列表的单条列表过长时可退化为 AVL 树或哈希表，把查询从 $O(n)$ 压到 $O(\log n)$ 甚至 $O(1)$；而邻接矩阵以空间换时间，本就贴着查询效率的上限。

速查地图：复杂度与源码路径一览

操作	时间复杂度	空间
加边 / 删边 / 查边	$O(1)$	$O(n^2)$
加顶点 / 删顶点	$O(n)$	$O(n^2)$

素材	相对路径
完整版源码	ru/codes/python/chapter_graph/graph_adjacency_matrix.py
Python Tutor 演示文件	ru/codes/pythontutor/chapter_graph/graph_adjacency_matrix.md
章节文档	ru/docs/chapter_graph/graph.md
邻接列表对照实现	ru/codes/python/chapter_graph/graph_adjacency_list.py

把 $O(1)$ 的边操作、$O(n)$ 的顶点操作和 $O(n^2)$ 的空间画像记牢，再配上上面四条路径，你既能读懂这份无向图邻接矩阵实现、能在本地跑通它，也能在真实场景里果断选对表示方式。

【免费下载链接】f3dFast and minimalist 3D viewer.项目地址: https://gitcode.com/GitHub_Trending/f3/f3d