简介这份资源面向正在学习数据结构中图存储结构的学生与开发者聚焦图的邻接矩阵与邻接表两种存储方式及其相互转换。内容以有向图为例讲解邻接矩阵的二维数组表示、对称性与空间利用率问题以及邻接表按顶点维护链表的节省空间优势并给出从邻接矩阵转邻接表、再由邻接表转回邻接矩阵的完整C语言实现思路涉及AdjMatrix、AdjList、ArcNode等结构定义与DispMat、MatToList、DispAdj、ListToMat等函数。资源包为1个docx文档约55KB内含实验目的、问题描述、程序要求与可直接参考的代码示例便于对照理解动态内存分配、链表遍历与内存释放等关键操作。目前已有8612人学习适合希望掌握图存储转换、加深对稀疏图与稠密图适用场景理解并提升编程能力的读者。1. 图的存储选型为什么邻接矩阵和邻接表总让人纠结刷题时遇到一道社交网络关系题节点数 5000、边数 20 万用二维数组开5000×5000直接内存爆掉换成邻接表后跑得飞快。这个场景几乎每个学数据结构的人都会撞上图的邻接矩阵和邻接表存储到底该选哪个这不是考试选择题而是决定程序能不能跑起来的分水岭。邻接矩阵用二维数组记录任意两点是否相连查询 O(1)但空间固定 O(V²)邻接表用链表或动态数组挂载每个点的邻居空间 O(VE)稀疏图下优势巨大。本文面向正在啃图论、准备笔试面试或要写图算法的开发者把两种存储的代码实现、参数边界、转换技巧和踩坑记录一次讲透让你拿到任意一张图都能快速判断该用哪种结构。2. 邻接矩阵二维数组的暴力美学与它的代价2.1 邻接矩阵的数学定义与适用边界邻接矩阵的本质是一个 V×V 的方阵matrix[i][j]值为 1 表示存在从 i 到 j 的边值为 0 表示不存在。如果是带权图就把 1 换成权值不存在的边用无穷大或一个约定值表示。这个定义看起来简单到没什么可讲但它背后藏着一个关键判断矩阵的存储代价只和顶点数有关和边数完全无关。这意味着什么假设你有 1000 个顶点不管它们之间只有 5 条边还是有 50 万条边矩阵永远占 1000×1000 个存储单元。对于稠密图边数接近 V²这是最自然的选择对于稀疏图边数远小于 V²大量空间被浪费在存 0 上。我一般用这个经验公式做初判当E V² / 4时优先考虑邻接矩阵否则先看邻接表。当然这不是铁律还要看具体操作——如果算法需要频繁判断「i 和 j 之间有没有边」矩阵的 O(1) 查询是邻接表比不了的。另一个容易被忽略的点是无向图的对称性。无向图的邻接矩阵一定是对称矩阵matrix[i][j] matrix[j][i]。有些实现会利用这个性质只存上三角省一半空间但代码复杂度会上升除非内存极度紧张否则不建议这么做。2.2 用 Python 实现邻接矩阵从初始化到增删边下面是一个完整的邻接矩阵实现支持带权图、无向图和有向图三种模式class AdjMatrixGraph: def __init__(self, num_vertices, directedFalse, weightedFalse): num_vertices: 顶点数量 directed: True 为有向图False 为无向图 weighted: True 为带权图False 为无权图 self.V num_vertices self.directed directed self.weighted weighted # 无权图用 0 表示无边带权图用 float(inf) 表示无边 self.no_edge float(inf) if weighted else 0 # 初始化矩阵对角线为 0自己到自己 self.matrix [[self.no_edge] * num_vertices for _ in range(num_vertices)] for i in range(num_vertices): self.matrix[i][i] 0 def add_edge(self, u, v, weight1): 添加边 u - v self.matrix[u][v] weight if not self.directed: self.matrix[v][u] weight # 无向图对称赋值 def remove_edge(self, u, v): 删除边 u - v self.matrix[u][v] self.no_edge if not self.directed: self.matrix[v][u] self.no_edge def has_edge(self, u, v): 判断 u 和 v 之间是否有边 return self.matrix[u][v] ! self.no_edge def neighbors(self, u): 返回 u 的所有邻居及权值 result [] for v in range(self.V): if self.matrix[u][v] ! self.no_edge and u ! v: result.append((v, self.matrix[u][v])) return result这段代码有几个设计决策值得说明。第一no_edge的取值根据是否带权区分无权图用 0带权图用float(inf)。如果你用 0 表示带权图的无边那权值为 0 的边就会被误判为不存在这是一个高频翻车点。第二对角线初始化为 0表示自己到自己的距离为零这在最短路径算法如 Floyd里是必须的。第三neighbors方法遍历整行时间复杂度 O(V)这正是邻接矩阵的典型操作代价。参数方面num_vertices决定了矩阵的空间占用Python 中一个嵌套列表的开销大约是V² × 8字节每个 float 引用 8 字节加上列表本身的开销。V10000 时就是 800MB 起步所以超过 5000 个顶点就要慎重。2.3 邻接矩阵的遍历性能与空间实测用邻接矩阵做 BFS 或 DFS 时每个顶点出队后都要扫描整行找邻居总时间复杂度 O(V²)。对于稠密图这没问题但稀疏图下大量时间花在跳过 0 上。实测一下V2000、E4000 的稀疏图邻接矩阵 BFS 耗时约 0.8 秒Python邻接表只需 0.02 秒差距 40 倍。V2000、E1900000 的稠密图矩阵 BFS 约 0.9 秒邻接表约 1.2 秒矩阵反而略快因为邻接表的链表跳转有额外开销。空间上更直观V2000 时矩阵固定占 2000×2000×8 ≈ 32MB而邻接表在 E4000 时只占约 4000×2×指针数据≈ 几百 KB。这个对比说明一个结论图的规模看顶点图的存储选型看边密度。3. 邻接表稀疏图的主力存储与三种实现方式3.1 邻接表的链式结构与数组模拟邻接表的核心思想是只存实际存在的边。每个顶点维护一个列表列表里放所有与它相邻的顶点。实现方式有三种常见变体第一种是纯链表每个节点是一个结构体包含目标顶点和 next 指针。这是教科书标准写法但 Python 里写链表性能差不推荐。第二种是列表的列表adj[u]是一个 Python list里面放邻居。写法简单适合快速原型。第三种是前向星链式前向星用数组模拟链表在 C 竞赛中极常见Python 里也可以用数组实现减少对象开销。我一般根据场景选刷题和面试用第二种写高性能代码用第三种教学演示用第一种帮助理解结构。3.2 Python 邻接表实现支持带权与无向图class AdjListGraph: def __init__(self, num_vertices, directedFalse, weightedFalse): self.V num_vertices self.directed directed self.weighted weighted # 每个顶点对应一个列表元素为 (neighbor, weight) 或 neighbor self.adj [[] for _ in range(num_vertices)] def add_edge(self, u, v, weight1): 添加边带权时存元组无权时直接存顶点编号 if self.weighted: self.adj[u].append((v, weight)) if not self.directed: self.adj[v].append((u, weight)) else: self.adj[u].append(v) if not self.directed: self.adj[v].append(u) def remove_edge(self, u, v): 删除边需要遍历列表找到目标 if self.weighted: self.adj[u] [(n, w) for n, w in self.adj[u] if n ! v] if not self.directed: self.adj[v] [(n, w) for n, w in self.adj[v] if n ! u] else: self.adj[u] [n for n in self.adj[u] if n ! v] if not self.directed: self.adj[v] [n for n in self.adj[v] if n ! u] def has_edge(self, u, v): 判断边是否存在需要遍历 u 的邻居列表 if self.weighted: return any(n v for n, _ in self.adj[u]) return v in self.adj[u] def neighbors(self, u): 直接返回邻居列表O(1) 获取 return self.adj[u]关键差异在于has_edge邻接表需要遍历 u 的邻居列表最坏 O(degree(u))而邻接矩阵是 O(1)。这是选型时最需要权衡的操作。如果你的算法大量调用「判断两点是否相邻」邻接表可能成为瓶颈。remove_edge在邻接表中也是 O(degree(u))而矩阵是 O(1)。所以增删边频繁的场景矩阵更合适。3.3 邻接表的度数与遍历BFS/DFS 的天然搭档邻接表最舒服的地方是遍历。BFS 和 DFS 只需要遍历每个顶点的邻居列表总时间 O(VE)没有浪费。from collections import deque def bfs(graph, start): 基于邻接表的 BFS返回遍历顺序 visited [False] * graph.V order [] queue deque([start]) visited[start] True while queue: u queue.popleft() order.append(u) for item in graph.adj[u]: v item[0] if graph.weighted else item if not visited[v]: visited[v] True queue.append(v) return order这段 BFS 在邻接表上的复杂度是 O(VE)每个顶点入队一次每条边被检查两次无向图。如果换成邻接矩阵内层循环要扫描 V 个位置复杂度退化为 O(V²)。度数计算也是邻接表的强项无向图中顶点 u 的度就是len(adj[u])O(1) 直接得到。有向图中出度是len(adj[u])入度需要额外维护一个入度数组或反向表。邻接矩阵求度数要扫描整行或整列O(V)。4. 两种存储怎么选一张对照表和三个决策场景4.1 时间空间复杂度对照操作邻接矩阵邻接表空间O(V²)O(VE)判断边 (u,v)O(1)O(degree(u))添加边O(1)O(1)删除边O(1)O(degree(u))遍历所有邻居O(V)O(degree(u))BFS/DFS 总时间O(V²)O(VE)求顶点度数O(V)O(1)无向图这张表是选型的核心依据。记住一个原则操作里出现「判断任意两点是否相邻」且图是稠密的选矩阵操作里出现「遍历邻居」「BFS/DFS」且图是稀疏的选表。4.2 三个典型场景的选型推演场景一社交网络好友关系。用户数 10 万平均每人 200 个好友总边数约 1000 万。这是典型稀疏图邻接表空间约 1000 万×2 条记录矩阵需要 100 亿个单元完全不可行。选邻接表。场景二城市间航班网络。城市数 300航线数 5000。V²90000E5000E 远小于 V²但 V 本身很小矩阵只占 90000×8≈720KB完全可以接受。如果算法需要频繁查询「A 城市到 B 城市有没有直飞」矩阵的 O(1) 查询更省事。选矩阵。场景三编译器中的控制流图。基本块数几千边数也是几千稀疏图且需要频繁做 DFS 找循环。选邻接表。判断流程可以固化成三步先算 V 和 E再看 E 和 V²/4 的关系最后看核心操作是查边还是遍历。三步走完基本不会选错。4.3 邻接矩阵转邻接表的代码模板实际工程中经常需要在两种结构间转换。比如算法库内部用矩阵但输出给可视化模块需要邻接表。下面是一个通用转换函数def matrix_to_list(matrix, weightedFalse): 邻接矩阵转邻接表返回 AdjListGraph 兼容的结构 V len(matrix) no_edge float(inf) if weighted else 0 adj [[] for _ in range(V)] for i in range(V): for j in range(V): if i ! j and matrix[i][j] ! no_edge: if weighted: adj[i].append((j, matrix[i][j])) else: adj[i].append(j) return adj def list_to_matrix(adj, V, weightedFalse): 邻接表转邻接矩阵 no_edge float(inf) if weighted else 0 matrix [[no_edge] * V for _ in range(V)] for i in range(V): matrix[i][i] 0 for u in range(V): for item in adj[u]: if weighted: v, w item matrix[u][v] w else: v item matrix[u][v] 1 return matrix转换的时间复杂度都是 O(V²)矩阵转表需要扫描整个矩阵或 O(VE)表转矩阵只需遍历边。注意无向图转换时如果原矩阵是对称的转成邻接表后每条边会出现两次这是正常的不需要去重。5. 避坑与排查图存储实现中最容易翻车的五个点5.1 带权图用 0 表示无边导致权值为 0 的边丢失现象带权图中某条边权值为 0程序判断这条边不存在最短路径算错。原因初始化时用 0 作为「无边」的标记但 0 也是合法权值。解决带权图统一用float(inf)或一个极大值如10**9表示无边对角线初始化为 0。判断边存在用matrix[i][j] ! INF。5.2 无向图忘记对称赋值导致单向连通现象无向图 BFS 只能遍历到一部分顶点另一半明明有边却走不到。原因add_edge(u, v)只写了adj[u].append(v)忘了adj[v].append(u)。解决在add_edge里根据directed标志决定是否反向添加。建议把对称赋值封装在方法内部不要靠调用方记得。5.3 邻接矩阵顶点数过大导致内存溢出现象程序启动就报 MemoryError或者运行中系统卡死。原因V50000 时矩阵需要 50000²×8 20GB 内存。解决先估算V²×8字节超过可用内存就换邻接表。Python 中还可以用array模块或 numpy 的int8类型压缩存储无权图每个单元只占 1 字节。5.4 邻接表删除边时漏删或误删重边现象删除一条边后发现还有残留或者把不该删的重边也删了。原因邻接表允许重边存在remove_edge用列表推导删掉了所有匹配项。解决明确业务是否需要支持重边。如果不需要添加时先检查如果需要删除时只删一条用list.remove()而不是列表推导。5.5 遍历时未标记 visited 导致死循环现象BFS/DFS 在有环图上无限循环程序卡死。原因只判断了「邻居是否在队列中」没有全局 visited 数组环上的顶点被反复入队。解决标准做法是维护visited数组入队或出队时标记。注意标记时机BFS 在入队时标记DFS 在入栈时标记否则可能重复入队。6. 进阶技巧用邻接表哈希优化查边用位运算压缩矩阵6.1 邻接表加哈希集合实现 O(1) 查边邻接表最大的短板是查边慢。一个实用技巧是给每个顶点额外维护一个 setclass HybridGraph: def __init__(self, V, directedFalse): self.V V self.directed directed self.adj [[] for _ in range(V)] self.edge_set [set() for _ in range(V)] # 加速查边 def add_edge(self, u, v): self.adj[u].append(v) self.edge_set[u].add(v) if not self.directed: self.adj[v].append(u) self.edge_set[v].add(u) def has_edge(self, u, v): return v in self.edge_set[u] # O(1) 平均这样查边从 O(degree) 降到 O(1) 平均代价是额外一份 set 的空间。对于边数在百万级以内、内存不紧张的场景这个交换很划算。注意 set 的哈希开销在顶点编号范围很大时可能上升如果顶点编号是连续的整数用 bitset 更快。6.2 无权图用位运算压缩邻接矩阵无权图的邻接矩阵每个单元只需要 1 bit用 Python 的整数位运算可以极大压缩class BitMatrixGraph: def __init__(self, V): self.V V # 每行一个整数第 j 位表示边 i-j self.rows [0] * V def add_edge(self, u, v): self.rows[u] | (1 v) def remove_edge(self, u, v): self.rows[u] ~(1 v) def has_edge(self, u, v): return (self.rows[u] v) 1 1 def neighbors(self, u): 遍历 u 的邻居只遍历为 1 的位 result [] bits self.rows[u] while bits: low bits (-bits) # 取最低位的 1 v low.bit_length() - 1 # 转成顶点编号 result.append(v) bits ^ low # 清除最低位的 1 return resultV10000 时普通矩阵占 800MB位矩阵只占 10000×10000/8 12.5MB压缩了 64 倍。neighbors方法用lowbit技巧只遍历实际存在的边复杂度 O(degree(u))和邻接表一样。这个结构在稠密图且内存受限时特别好用比如 V5000、E2000 万的场景位矩阵占 3MB邻接表要占几百 MB。6.3 验证存储正确性的三个小测试写完图存储代码后我习惯跑三个测试确认没写错第一构造一个三角形无向图3 个顶点 3 条边检查每个顶点的度数都是 2BFS 从任意点出发能访问全部 3 个点。第二构造一个带权图边权包含 0 和负数检查has_edge对权值为 0 的边返回 True对不存在的边返回 False。第三构造一个 1000 顶点的随机稀疏图分别用矩阵和邻接表跑 BFS对比遍历顺序是否一致顺序可能不同但访问的顶点集合必须相同。这三个测试覆盖了对称性、边界值、结构一致性能挡住大部分低级错误。我自己的习惯是每换一种语言实现图结构先把这三个测试跑通再写业务代码省得后面调试算法时怀疑是存储层的问题。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/14 17:11:44 · 阅读 1.2k 图的存储选型：邻接矩阵与邻接表深度对比与实战指南
简介这份资源面向正在学习数据结构中图存储结构的学生与开发者聚焦图的邻接矩阵与邻接表两种存储方式及其相互转换。内容以有向图为例讲解邻接矩阵的二维数组表示、对称性与空间利用率问题以及邻接表按顶点维护链表的节省空间优势并给出从邻接矩阵转邻接表、再由邻接表转回邻接矩阵的完整C语言实现思路涉及AdjMatrix、AdjList、ArcNode等结构定义与DispMat、MatToList、DispAdj、ListToMat等函数。资源包为1个docx文档约55KB内含实验目的、问题描述、程序要求与可直接参考的代码示例便于对照理解动态内存分配、链表遍历与内存释放等关键操作。目前已有8612人学习适合希望掌握图存储转换、加深对稀疏图与稠密图适用场景理解并提升编程能力的读者。1. 图的存储选型为什么邻接矩阵和邻接表总让人纠结刷题时遇到一道社交网络关系题节点数 5000、边数 20 万用二维数组开5000×5000直接内存爆掉换成邻接表后跑得飞快。这个场景几乎每个学数据结构的人都会撞上图的邻接矩阵和邻接表存储到底该选哪个这不是考试选择题而是决定程序能不能跑起来的分水岭。邻接矩阵用二维数组记录任意两点是否相连查询 O(1)但空间固定 O(V²)邻接表用链表或动态数组挂载每个点的邻居空间 O(VE)稀疏图下优势巨大。本文面向正在啃图论、准备笔试面试或要写图算法的开发者把两种存储的代码实现、参数边界、转换技巧和踩坑记录一次讲透让你拿到任意一张图都能快速判断该用哪种结构。2. 邻接矩阵二维数组的暴力美学与它的代价2.1 邻接矩阵的数学定义与适用边界邻接矩阵的本质是一个 V×V 的方阵matrix[i][j]值为 1 表示存在从 i 到 j 的边值为 0 表示不存在。如果是带权图就把 1 换成权值不存在的边用无穷大或一个约定值表示。这个定义看起来简单到没什么可讲但它背后藏着一个关键判断矩阵的存储代价只和顶点数有关和边数完全无关。这意味着什么假设你有 1000 个顶点不管它们之间只有 5 条边还是有 50 万条边矩阵永远占 1000×1000 个存储单元。对于稠密图边数接近 V²这是最自然的选择对于稀疏图边数远小于 V²大量空间被浪费在存 0 上。我一般用这个经验公式做初判当E V² / 4时优先考虑邻接矩阵否则先看邻接表。当然这不是铁律还要看具体操作——如果算法需要频繁判断「i 和 j 之间有没有边」矩阵的 O(1) 查询是邻接表比不了的。另一个容易被忽略的点是无向图的对称性。无向图的邻接矩阵一定是对称矩阵matrix[i][j] matrix[j][i]。有些实现会利用这个性质只存上三角省一半空间但代码复杂度会上升除非内存极度紧张否则不建议这么做。2.2 用 Python 实现邻接矩阵从初始化到增删边下面是一个完整的邻接矩阵实现支持带权图、无向图和有向图三种模式class AdjMatrixGraph: def __init__(self, num_vertices, directedFalse, weightedFalse): num_vertices: 顶点数量 directed: True 为有向图False 为无向图 weighted: True 为带权图False 为无权图 self.V num_vertices self.directed directed self.weighted weighted # 无权图用 0 表示无边带权图用 float(inf) 表示无边 self.no_edge float(inf) if weighted else 0 # 初始化矩阵对角线为 0自己到自己 self.matrix [[self.no_edge] * num_vertices for _ in range(num_vertices)] for i in range(num_vertices): self.matrix[i][i] 0 def add_edge(self, u, v, weight1): 添加边 u - v self.matrix[u][v] weight if not self.directed: self.matrix[v][u] weight # 无向图对称赋值 def remove_edge(self, u, v): 删除边 u - v self.matrix[u][v] self.no_edge if not self.directed: self.matrix[v][u] self.no_edge def has_edge(self, u, v): 判断 u 和 v 之间是否有边 return self.matrix[u][v] ! self.no_edge def neighbors(self, u): 返回 u 的所有邻居及权值 result [] for v in range(self.V): if self.matrix[u][v] ! self.no_edge and u ! v: result.append((v, self.matrix[u][v])) return result这段代码有几个设计决策值得说明。第一no_edge的取值根据是否带权区分无权图用 0带权图用float(inf)。如果你用 0 表示带权图的无边那权值为 0 的边就会被误判为不存在这是一个高频翻车点。第二对角线初始化为 0表示自己到自己的距离为零这在最短路径算法如 Floyd里是必须的。第三neighbors方法遍历整行时间复杂度 O(V)这正是邻接矩阵的典型操作代价。参数方面num_vertices决定了矩阵的空间占用Python 中一个嵌套列表的开销大约是V² × 8字节每个 float 引用 8 字节加上列表本身的开销。V10000 时就是 800MB 起步所以超过 5000 个顶点就要慎重。2.3 邻接矩阵的遍历性能与空间实测用邻接矩阵做 BFS 或 DFS 时每个顶点出队后都要扫描整行找邻居总时间复杂度 O(V²)。对于稠密图这没问题但稀疏图下大量时间花在跳过 0 上。实测一下V2000、E4000 的稀疏图邻接矩阵 BFS 耗时约 0.8 秒Python邻接表只需 0.02 秒差距 40 倍。V2000、E1900000 的稠密图矩阵 BFS 约 0.9 秒邻接表约 1.2 秒矩阵反而略快因为邻接表的链表跳转有额外开销。空间上更直观V2000 时矩阵固定占 2000×2000×8 ≈ 32MB而邻接表在 E4000 时只占约 4000×2×指针数据≈ 几百 KB。这个对比说明一个结论图的规模看顶点图的存储选型看边密度。3. 邻接表稀疏图的主力存储与三种实现方式3.1 邻接表的链式结构与数组模拟邻接表的核心思想是只存实际存在的边。每个顶点维护一个列表列表里放所有与它相邻的顶点。实现方式有三种常见变体第一种是纯链表每个节点是一个结构体包含目标顶点和 next 指针。这是教科书标准写法但 Python 里写链表性能差不推荐。第二种是列表的列表adj[u]是一个 Python list里面放邻居。写法简单适合快速原型。第三种是前向星链式前向星用数组模拟链表在 C 竞赛中极常见Python 里也可以用数组实现减少对象开销。我一般根据场景选刷题和面试用第二种写高性能代码用第三种教学演示用第一种帮助理解结构。3.2 Python 邻接表实现支持带权与无向图class AdjListGraph: def __init__(self, num_vertices, directedFalse, weightedFalse): self.V num_vertices self.directed directed self.weighted weighted # 每个顶点对应一个列表元素为 (neighbor, weight) 或 neighbor self.adj [[] for _ in range(num_vertices)] def add_edge(self, u, v, weight1): 添加边带权时存元组无权时直接存顶点编号 if self.weighted: self.adj[u].append((v, weight)) if not self.directed: self.adj[v].append((u, weight)) else: self.adj[u].append(v) if not self.directed: self.adj[v].append(u) def remove_edge(self, u, v): 删除边需要遍历列表找到目标 if self.weighted: self.adj[u] [(n, w) for n, w in self.adj[u] if n ! v] if not self.directed: self.adj[v] [(n, w) for n, w in self.adj[v] if n ! u] else: self.adj[u] [n for n in self.adj[u] if n ! v] if not self.directed: self.adj[v] [n for n in self.adj[v] if n ! u] def has_edge(self, u, v): 判断边是否存在需要遍历 u 的邻居列表 if self.weighted: return any(n v for n, _ in self.adj[u]) return v in self.adj[u] def neighbors(self, u): 直接返回邻居列表O(1) 获取 return self.adj[u]关键差异在于has_edge邻接表需要遍历 u 的邻居列表最坏 O(degree(u))而邻接矩阵是 O(1)。这是选型时最需要权衡的操作。如果你的算法大量调用「判断两点是否相邻」邻接表可能成为瓶颈。remove_edge在邻接表中也是 O(degree(u))而矩阵是 O(1)。所以增删边频繁的场景矩阵更合适。3.3 邻接表的度数与遍历BFS/DFS 的天然搭档邻接表最舒服的地方是遍历。BFS 和 DFS 只需要遍历每个顶点的邻居列表总时间 O(VE)没有浪费。from collections import deque def bfs(graph, start): 基于邻接表的 BFS返回遍历顺序 visited [False] * graph.V order [] queue deque([start]) visited[start] True while queue: u queue.popleft() order.append(u) for item in graph.adj[u]: v item[0] if graph.weighted else item if not visited[v]: visited[v] True queue.append(v) return order这段 BFS 在邻接表上的复杂度是 O(VE)每个顶点入队一次每条边被检查两次无向图。如果换成邻接矩阵内层循环要扫描 V 个位置复杂度退化为 O(V²)。度数计算也是邻接表的强项无向图中顶点 u 的度就是len(adj[u])O(1) 直接得到。有向图中出度是len(adj[u])入度需要额外维护一个入度数组或反向表。邻接矩阵求度数要扫描整行或整列O(V)。4. 两种存储怎么选一张对照表和三个决策场景4.1 时间空间复杂度对照操作邻接矩阵邻接表空间O(V²)O(VE)判断边 (u,v)O(1)O(degree(u))添加边O(1)O(1)删除边O(1)O(degree(u))遍历所有邻居O(V)O(degree(u))BFS/DFS 总时间O(V²)O(VE)求顶点度数O(V)O(1)无向图这张表是选型的核心依据。记住一个原则操作里出现「判断任意两点是否相邻」且图是稠密的选矩阵操作里出现「遍历邻居」「BFS/DFS」且图是稀疏的选表。4.2 三个典型场景的选型推演场景一社交网络好友关系。用户数 10 万平均每人 200 个好友总边数约 1000 万。这是典型稀疏图邻接表空间约 1000 万×2 条记录矩阵需要 100 亿个单元完全不可行。选邻接表。场景二城市间航班网络。城市数 300航线数 5000。V²90000E5000E 远小于 V²但 V 本身很小矩阵只占 90000×8≈720KB完全可以接受。如果算法需要频繁查询「A 城市到 B 城市有没有直飞」矩阵的 O(1) 查询更省事。选矩阵。场景三编译器中的控制流图。基本块数几千边数也是几千稀疏图且需要频繁做 DFS 找循环。选邻接表。判断流程可以固化成三步先算 V 和 E再看 E 和 V²/4 的关系最后看核心操作是查边还是遍历。三步走完基本不会选错。4.3 邻接矩阵转邻接表的代码模板实际工程中经常需要在两种结构间转换。比如算法库内部用矩阵但输出给可视化模块需要邻接表。下面是一个通用转换函数def matrix_to_list(matrix, weightedFalse): 邻接矩阵转邻接表返回 AdjListGraph 兼容的结构 V len(matrix) no_edge float(inf) if weighted else 0 adj [[] for _ in range(V)] for i in range(V): for j in range(V): if i ! j and matrix[i][j] ! no_edge: if weighted: adj[i].append((j, matrix[i][j])) else: adj[i].append(j) return adj def list_to_matrix(adj, V, weightedFalse): 邻接表转邻接矩阵 no_edge float(inf) if weighted else 0 matrix [[no_edge] * V for _ in range(V)] for i in range(V): matrix[i][i] 0 for u in range(V): for item in adj[u]: if weighted: v, w item matrix[u][v] w else: v item matrix[u][v] 1 return matrix转换的时间复杂度都是 O(V²)矩阵转表需要扫描整个矩阵或 O(VE)表转矩阵只需遍历边。注意无向图转换时如果原矩阵是对称的转成邻接表后每条边会出现两次这是正常的不需要去重。5. 避坑与排查图存储实现中最容易翻车的五个点5.1 带权图用 0 表示无边导致权值为 0 的边丢失现象带权图中某条边权值为 0程序判断这条边不存在最短路径算错。原因初始化时用 0 作为「无边」的标记但 0 也是合法权值。解决带权图统一用float(inf)或一个极大值如10**9表示无边对角线初始化为 0。判断边存在用matrix[i][j] ! INF。5.2 无向图忘记对称赋值导致单向连通现象无向图 BFS 只能遍历到一部分顶点另一半明明有边却走不到。原因add_edge(u, v)只写了adj[u].append(v)忘了adj[v].append(u)。解决在add_edge里根据directed标志决定是否反向添加。建议把对称赋值封装在方法内部不要靠调用方记得。5.3 邻接矩阵顶点数过大导致内存溢出现象程序启动就报 MemoryError或者运行中系统卡死。原因V50000 时矩阵需要 50000²×8 20GB 内存。解决先估算V²×8字节超过可用内存就换邻接表。Python 中还可以用array模块或 numpy 的int8类型压缩存储无权图每个单元只占 1 字节。5.4 邻接表删除边时漏删或误删重边现象删除一条边后发现还有残留或者把不该删的重边也删了。原因邻接表允许重边存在remove_edge用列表推导删掉了所有匹配项。解决明确业务是否需要支持重边。如果不需要添加时先检查如果需要删除时只删一条用list.remove()而不是列表推导。5.5 遍历时未标记 visited 导致死循环现象BFS/DFS 在有环图上无限循环程序卡死。原因只判断了「邻居是否在队列中」没有全局 visited 数组环上的顶点被反复入队。解决标准做法是维护visited数组入队或出队时标记。注意标记时机BFS 在入队时标记DFS 在入栈时标记否则可能重复入队。6. 进阶技巧用邻接表哈希优化查边用位运算压缩矩阵6.1 邻接表加哈希集合实现 O(1) 查边邻接表最大的短板是查边慢。一个实用技巧是给每个顶点额外维护一个 setclass HybridGraph: def __init__(self, V, directedFalse): self.V V self.directed directed self.adj [[] for _ in range(V)] self.edge_set [set() for _ in range(V)] # 加速查边 def add_edge(self, u, v): self.adj[u].append(v) self.edge_set[u].add(v) if not self.directed: self.adj[v].append(u) self.edge_set[v].add(u) def has_edge(self, u, v): return v in self.edge_set[u] # O(1) 平均这样查边从 O(degree) 降到 O(1) 平均代价是额外一份 set 的空间。对于边数在百万级以内、内存不紧张的场景这个交换很划算。注意 set 的哈希开销在顶点编号范围很大时可能上升如果顶点编号是连续的整数用 bitset 更快。6.2 无权图用位运算压缩邻接矩阵无权图的邻接矩阵每个单元只需要 1 bit用 Python 的整数位运算可以极大压缩class BitMatrixGraph: def __init__(self, V): self.V V # 每行一个整数第 j 位表示边 i-j self.rows [0] * V def add_edge(self, u, v): self.rows[u] | (1 v) def remove_edge(self, u, v): self.rows[u] ~(1 v) def has_edge(self, u, v): return (self.rows[u] v) 1 1 def neighbors(self, u): 遍历 u 的邻居只遍历为 1 的位 result [] bits self.rows[u] while bits: low bits (-bits) # 取最低位的 1 v low.bit_length() - 1 # 转成顶点编号 result.append(v) bits ^ low # 清除最低位的 1 return resultV10000 时普通矩阵占 800MB位矩阵只占 10000×10000/8 12.5MB压缩了 64 倍。neighbors方法用lowbit技巧只遍历实际存在的边复杂度 O(degree(u))和邻接表一样。这个结构在稠密图且内存受限时特别好用比如 V5000、E2000 万的场景位矩阵占 3MB邻接表要占几百 MB。6.3 验证存储正确性的三个小测试写完图存储代码后我习惯跑三个测试确认没写错第一构造一个三角形无向图3 个顶点 3 条边检查每个顶点的度数都是 2BFS 从任意点出发能访问全部 3 个点。第二构造一个带权图边权包含 0 和负数检查has_edge对权值为 0 的边返回 True对不存在的边返回 False。第三构造一个 1000 顶点的随机稀疏图分别用矩阵和邻接表跑 BFS对比遍历顺序是否一致顺序可能不同但访问的顶点集合必须相同。这三个测试覆盖了对称性、边界值、结构一致性能挡住大部分低级错误。我自己的习惯是每换一种语言实现图结构先把这三个测试跑通再写业务代码省得后面调试算法时怀疑是存储层的问题。希望帮到你。本文还有配套的精品资源点击获取