邻接矩阵怎么存无向图5 分钟读懂 GraphAdjMat 的增删边与本地运行【免费下载链接】f3dFast and minimalist 3D viewer.项目地址: https://gitcode.com/GitHub_Trending/f3/f3dhello-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$ 长成 $(n1) \times (n1)$。新顶点暂时和谁都「无边」所以新行、新列必须全 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×51add_edge(0, 2)[1, 3, 2, 5, 4]5×52remove_edge(0, 1)[1, 3, 2, 5, 4]5×53add_vertex(6)[1, 3, 2, 5, 4, 6]6×64remove_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.pyPython 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考